n个环上的点，用n种颜 {MOD}染 {MOD}，模p。 只考虑绕中点的旋转，根据polya定理，答案为：(∑n^gcd(n,i))/n   1<=i<=n; 暴力超时。 我们考虑gcd(n,i)==x,的满足条件的i的个数。    个数设为t，那么这些的和即为 t*(n^x); gcd(n,i)==x,  gcd(n/x,i/x)==1 ,  满足条件的i的个数，即为n/x的欧拉函数值。 然后就可以搞了。 质数打表，优化欧拉函数。 #include #include #include #include #include #include using namespace std; #define ll long long #define N 50000 //质数范围 int prime[100000]; //prime[0]=2,prime[1]=3,prime[2]=5,…… void init_prime() { int i, j; for(i = 2;i <= sqrt(N*1.0); ++i) { if(!prime[i]) for(j = i * i; j < N; j += i) prime[j] = 1; } j = 0; for(i = 2;i <= N; ++i) if(!prime[i]) prime[j++] = i; } int eular(int n){ int ret=1,i,j=0; for (i=0;prime[i]*prime[i]<=n;i++) if (n%prime[i]==0){ n/=prime[i],ret*=prime[i]-1; while (n%prime[i]==0) n/=prime[i],ret*=prime[i]; } if (n>1) ret*=n-1; return ret; } int qpow(int n,int m ,int p) { int ans=1; n%=p; while(m) { if(m&1) ans=ans*n%p; m>>=1; n=n*n%p; } return ans; } int main() { int t; init_prime(); scanf("%d",&t); while(t--) { int n,p,i; scanf("%d%d",&n,&p); int ans=0; for(i=1;i*i