8.24

ABC212G

题意：

给定数字\(P\)

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

\(P\leq 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;
}
/*

*/