和上题一样，只考虑旋转等价，只不过颜色和珠子$1e9$
一样的式子
$\sum\limits_{i=1}^n m^{gcd(i,n)}$
然后按$gcd$分类，枚举$n$的约数
如果这个也化不出来我莫比乌斯反演白♂学了
最后结果为
$\frac{n}{1}\sum\limits_{d \mid n}n^d \phi (\frac{n}{d})$
然后$\frac{n}{1}$可以放进去避免除法
然后欧拉函数显然需要现算，上午$T$了，改成筛质数之后算就好了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+5; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f; } int n,P; int p[N]; bool notp[N]; void sieve(int n){ for(int i=2;i<=n;i++){ if(!notp[i]) p[++p[0]]=i; for(int j=1;j<=p[0]&&i*p[j]<=n;j++){ notp[i*p[j]]=1; if(i%p[j]==0) break; } } } inline int Pow(int a,int b){ int re=1; a%=P; for(;b;b>>=1,a=a*a%P) if(b&1) re=re*a%P; return re; } inline int phi(int n){ int re=n,m=sqrt(n); for(int i=1;i<=p[0]&&p[i]<=m&&p[i]<=n;i++) if(n%p[i]==0){ re=re/p[i]*(p[i]-1); while(n%p[i]==0) n/=p[i]; } if(n>1) re=re/n*(n-1); return re%P; } int main(){ freopen("in","r",stdin); int T=read(); sieve(32000); while(T--){ n=read();P=read(); int m=sqrt(n),ans=0; for(int i=1;i<=m;i++) if(n%i==0){ ans+=Pow(n,i-1)*phi(n/i)%P; if(i*i!=n) ans+=Pow(n,n/i-1)*phi(i)%P; ans%=P; } printf("%d\n",ans); } }
原文：http://www.cnblogs.com/candy99/p/6478733.html