【数论】Codeforces1027G X-mouse in the Campus

分析：

显然，i->ix(mod m)连一条边，则最终一定会形成若干个环，并且，环上每个点与m的gcd值必定相同。并且，gcd值相同的环大小也一定相同。

所以，如果能算出对于所有数中，与m的gcd为d的个数$f(d)$，并算出相应的当gcd为d时的每个环的大小$l(d)$，那么答案就是$\sum \frac{f(d)}{l(d)}$

很容易发现，$f(d)=\phi (\frac{m}{d})$(就是欧拉函数的定义)
并且，由于l(d)是满足$x^{l(d)}\equiv 1(mod\frac{m}{d})$的最小正整数，所以$l(d)|\phi (\frac{m}{d})$，可以先枚举每一个d，计算相应的$\phi (\frac{m}{d})$。
然后枚举$\phi (\frac{m}{d})$的每个质因数，依次试着除下去即可（每次除之前先判断能否满足）。

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define SF scanf #define PF printf #define MAXN 100010 using namespace std; typedef long long ll; void get_prim(ll x,ll prim[],int &top){
     top=0;for(ll i=2;i*i<=x;i++){
     if(x%i==0){
     prim[++top]=i;while(x%i==0)x/=i;}}if(x!=1)prim[++top]=x;sort(prim+1,prim+1+top); } void get_fac(ll x,ll fac[],int &top){
     top=0;for(ll i=1;i*i<=x;i++){
     if(x%i==0){
     fac[++top]=i;if(i*i!=x)fac[++top]=x/i;}}sort(fac+1,fac+1+top); } ll mul(ll x,ll y,ll mod){
     ll res=(x*y-(ll)((double)x*y/mod+0.1)*mod)%mod;if(res<0)res+=mod;return res; } ll fsp(ll x,ll y,ll mod){
     x%=mod;ll res=1;while(y){
     if(y&1ll)res=mul(res,x,mod);x=mul(x,x,mod);y>>=1ll;}return res; } int tot,cnt; ll prims[MAXN],fact[MAXN],facs[MAXN]; ll Euler(ll x){
     for(int i=1;i<=tot;i++)if(x%prims[i]==0)x=x/prims[i]*(prims[i]-1ll);return x; } ll m,x; ll solve(){
     ll eul=Euler(m);ll res=0;int tt=0;if(eul>1)get_prim(eul,fact,tt);elsefact[++tt]=1;for(int i=1;i<=cnt;i++){
     ll f=Euler(facs[i]);ll l=f;if(l>1){
     for(int j=1;j<=tt;j++)while(l%fact[j]==0&&fsp(x,l/fact[j],facs[i])==1)l/=fact[j];}res=res+f/l;}return res; } int main(){
     SF("%lld%lld",&m,&x);get_fac(m,facs,cnt);get_prim(m,prims,tot);PF("%lld",solve()); }