[Codeforces 1139D] Steps to One

[题目链接]

https://codeforces.com/contest/1139/problem/D

[算法]

考虑dp

设fi表示现在gcd为i ，期望多少次gcd变为1

显然 , fi = (1 / m) * sigma{ fgcd(i , j) } + 1

直接转移是O(N ^ 2logN)的，显然不能通过

考虑在转移时枚举gcd ，显然gcd只可能是i的约数，可以在dp前O(NlogN)预处理每个数的约数

于是问题转化为求一个形如 : [1 , m]中有多少个数与i的gcd为j的问题

这等价于求 : [1 , m / j]中有多少个数与(i / j)的gcd为1

容斥原理计算即可

时间复杂度 : O(NlogN)( 有较大的常数 )

[代码]

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int P = 1e9 + ;

const int MAXP = 1e5 + ;

#define rint register int

int m , tot;

int f[MAXP] , prime[MAXP] , dp[MAXP];

vector< int > d[MAXP];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

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

{

    T 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 int exp_mod(int a , int n)

{

        int b = a , res = ;

        while (n > )

        {

                if (n & ) res = 1LL * res * b % P;

                b = 1LL * b * b % P;

                n >>= ;

        }

        return res;

}

inline int calc(int N , int M)

{

        vector< int > pr;

        int tmp = N / M;

        while (tmp != )

        {

                pr.push_back(f[tmp]);

                tmp /= f[tmp];

        }

        int sz = unique(pr.begin() , pr.end()) - pr.begin();

        int limit = m / M , res = ;

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

        {

                int sign =  , val = ;

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

                {

                        if (i & ( << j))

                        {

                                sign *= -;

                                val *= pr[j];

                        }

                }

                res += 1LL * sign * (limit / val);

        }

        return res;

}

int main()

{

        read(m);

        for (rint i = ; i <= m; ++i)

        {

                for (rint j = i; j <= m; j += i)

                {

                        d[j].push_back(i);

                }

        }

        for (rint i = ; i <= m; ++i)

        {

                if (!f[i])

                {

                        prime[++tot] = i;

                        f[i] = i;

                }

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

                {

                        int tmp = i * prime[j];

                        if (tmp >= MAXP) break;

                        f[tmp] = prime[j];

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

                }

        }

        dp[] = ;

        for (rint i = ; i <= m; ++i)

        {

                int res = ;

                for (unsigned j = ; j < d[i].size(); ++j)

                {

                        int D = d[i][j];

                        if (D != i) res = (res + 1LL * calc(i , D) * dp[D] % P) % P;

                }

                res = 1LL * res * exp_mod(m , P - ) % P;

                res = (res + ) % P;

                int fm = m - calc(i , i);

                res = 1LL * res * exp_mod(fm , P - ) % P * m % P;

                dp[i] = res;

        }

        int ans = ;

        for (rint i = ; i <= m; ++i) ans = (ans + 1LL * exp_mod(m , P - ) * dp[i] % P) % P;

        printf("%d\n" , ans);

        return ;

}

巴特西

[Codeforces 1139D] Steps to One

最新文章

热门文章