8.24

ABC212G

题意：

给定数字(P)

求有多少对((x,y))，满足(0leq x,y<P)，而且存在正整数(n)，满足(x^nequiv y (mod P))

(Pleq 10^{12})，(P)是质数

设(r)是(P)的原根

那么(x,y)可以表示为(x=r^a,y=r^b)

原式为(r^{an}=r^b (mod P))

把指数拿下来

(an=b (mod P-1))

设(n=P-1)

于是答案是((sum_{i=1}^{n}frac{n}{gcd(n,i)})+1)

加一是因为有((0,0))

按照套路，把枚举(i)变成枚举(g=gcd(n,i))

(sum_{g|n}frac{n}{g}*f(g))

其中(f(g)=sum_{i=1}^n[gcd(n,i)==g])

因为(n)的因数不多，假设数量为(m)，容斥求(f(g))的复杂度是(O(m^2))

所以复杂度就是(O(sqrt{n}+m^2))

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=1e6+10,mod=998244353,inv2=5e8+4,inf=2e15;
    void __init(int n=2000) {}
    
    inline void main()
    {
        int n;
        cin>>n;
        --n;
        int ans=1;
        vector<int> d;
        for(int i=1;i*i<=n;++i)
        {
            if(n%i==0)
            {
                d.emplace_back(i);
                if(i*i!=n) d.emplace_back(n/i);
            }
        }
        sort(d.begin(),d.end());
        int m=d.size();
        vector<int> f(m);
        for(int i=m-1;i>=0;--i)
        {
            f[i]=n/d[i];
            for(int j=i+1;j<m;++j)
            {
                if(d[j]%d[i]==0) f[i]-=f[j];
            }
        }
        for(int i=0;i<m;++i) ans=(ans+((n/d[i])%mod*(f[i]%mod))%mod)%mod;
        cout<<ans<<'n';
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    red::__init();
    int qwq=1; //cin>>qwq;
    while(qwq--) red::main();
    return 0;
}
/*

*/