[Codeforces 485F] Oppa Funcan Style Remastered

[题目链接]

https://codeforces.com/contest/986/problem/F

[算法]

不难发现，每个人都在且仅在一个简单环中，设这些环长的长度分别为

A1, A2 , A3 ... Alen, 那么有 :

1. A1 + A2 + A3 + .. + Alen = n

2. A1 , A2 , .. Alen为k的因子且大于或等于2

显然，每一个k的因数都可以分成若干个k的质因子之和，因此我们可以将问题转化为求是否存在：

B1P1 + B2P2 + ... BmPm = n （其中，m为质因子的个数）

当m = 0时，显然无解

当m = 1时，若n为P1的倍数，则有解，否则无解

当m = 2时 , 问题就转化为判断一个形如：Ax + By = C , GCD(A,B) = 1的不定方程是否有非负整数解，我们可以用拓展欧几里得或其他算法解决，不再赘述

当m >= 3时，显然，最小的质因子一定小于等于k ^ (1 / 3)， k最大时达到10 ^ 15 ，因此， k ^ (1 / 3)不会超过10 ^ 5 ，我们不妨建10^5个点，

若(i + Pi) mod P1 = j mod P1 , 则从i向j连一条权值为Pi的边。

然后我们从0号点开始单源最短路，求得的最短路Dist[i]表示通过k的质因子组合出的，模P1余i的数中最小的，显然，若n >= Dist[n mod P1] , 问题有解，否则无解。

下面我们分析整个算法的时间复杂度：

令Q = 50（不同的k的个数）

首先，为了减少在分解质因数上花费的时间，我们需要预处理质数 , 这将花费我们O( sqrt(K) ) )的时间，其中sqrt表示开根号

对于每个询问，我们需要将k分解质因数，我们需要花费O(Q * sqrt(K) / log(K))的时间 , 其中sqrt表示开根号

当m <= 2时我们需花费O(1) - O(logN)的时间，共需O(TlogN)的时间

当m >= 3时我们需要花费O(Q * k ^( 1 / 3) * logk)计算单源最短路（需使用高效的Dijkstra + 堆算法 )

综上，总时间复杂度为 : O( sqrt(k) + Q * ( sqrt(k) / log(k) + k ^ (1 / 3)logk ) + TlogN) , 可以通过此题

[代码]

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 1e18;

const ll MAXK = 1e15;

const ll INF = 4e18;

const int MAXV = 3.2e7 + ;

const int MAXP = 2e6 + ;

const int MAXF = 1e5 + ;

const int MAXQ = ;

const int MAXLOG = ;

ll n,k,tot,q;

int f[MAXV],prime[MAXP],cnt[MAXQ + ];

ll p[MAXQ + ][MAXLOG],dist[MAXQ + ][MAXF];

ll mem[MAXQ];

bool visited[MAXP];

template <typename T> inline void read(T &x)

{

    ll f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline ll exp_mod(ll a,ll n,ll p)

{

        ll res = , b = a;

        while (n > )

        {

                if (n & ) res = res * b % p;

                b = b * b % p;

                n >>= ;

        }

        return res;

}

int main()

{

        int T;

        read(T);

        for (int i = ; i < MAXV; i++)

        {

                if (!f[i]) prime[++tot] = f[i] = i;

                for (int j = ; j <= tot; j++)

                {

                        int tmp = i * prime[j];

                        if (tmp >= MAXV) break;

                        f[tmp] = prime[j];

                        if (f[i] == prime[j]) break;

                }

        }

        while (T--)

        {

                read(n); read(k);

                if (k == )

                {

                        printf("NO\n");

                        continue;

                }

                int pos = ;

                for (int i = ; i <= q; i++)

                        if (mem[i] == k) pos = i;

                if (!pos)

                {

                        pos = ++q;

                        mem[pos] = k;

                        cnt[pos] = ;

                        for (int i = ; 1ll * prime[i] * prime[i] <= k; i++)

                        {

                                if (k % prime[i] == )

                                {

                                        p[pos][++cnt[pos]] = prime[i];

                                        while (k % prime[i] == ) k /= prime[i];

                                }

                        }

                        if (k != ) p[pos][++cnt[pos]] = k;

                        if (cnt[pos] >= )

                        {

                                for (int i = ; i < p[pos][]; i++)

                                {

                                        dist[pos][i] = INF;

                                        visited[i] = false;

                                }

                                dist[pos][] = ;

                                static priority_queue< pair<ll,int> > q;

                                q.push(make_pair(,));

                                while (!q.empty())

                                {

                                        int u = q.top().second;

                                        q.pop();

                                        if (visited[u]) continue;

                                        visited[u] = true;

                                        for (int i = ; i <= cnt[pos]; i++)

                                        {

                                                int to = (u + p[pos][i]) % p[pos][];

                                                int w = p[pos][i];

                                                if (dist[pos][u] + w < dist[pos][to])

                                                {

                                                        dist[pos][to] = dist[pos][u] + w;

                                                        q.push(make_pair(-dist[pos][to],to));

                                                }

                                        }

                                }

                        }

                }

                if (cnt[pos] == )

                {

                        if (n % p[pos][] == )

                        {

                                printf("YES\n");

                                continue;

                        } else

                        {

                                printf("NO\n");

                                continue;

                        }

                }

                if (cnt[pos] == )

                {

                        ll b = n % p[pos][] * exp_mod(p[pos][] , p[pos][] - ,p[pos][]) % p[pos][];

                        if (b * p[pos][] <= n) printf("YES\n");

                        else printf("NO\n");

                        continue;

                }

                int val = n % p[pos][];

                if (n >= dist[pos][val]) printf("YES\n");

                else printf("NO\n");

        }

        return ;

}

巴特西

[Codeforces 485F] Oppa Funcan Style Remastered

最新文章

热门文章