参考：http://blog.csdn.net/u014492306/article/details/43196743 不知道怎么用欧拉函数优化，就找题解喽，感觉这个讲的挺好的 如果先把素数筛出来，再求欧拉函数就要快多了
#include <cstdio> int n,p; int res = 0; int euler(int num) { int ret = num; for(int i = 2; i*i <= num; ++i) { if(num%i == 0) { ret = ret/i*(i-1); while(num%i == 0) num /= i; } } if(num != 1) ret = ret/num*(num-1); return ret%p; } int modPow(int a, int b) { int ret = 1; a = a%p; while(b) { if(b&1) ret = ret*a%p; a = a*a%p; b >>= 1; } return ret; } void polya() { int ret = 0; for(int l = 1; l*l <= n; ++l) { if(n%l) continue; ret = (ret + euler(l)*modPow(n,n/l-1))%p;//这里n/l-1,最后就不用除以n了 if(l*l == n) break; ret = (ret + euler(n/l)*modPow(n,l-1))%p; } res = ret; } int main() { int X; scanf("%d",&X); while(X--) { scanf("%d%d",&n,&p); polya(); printf("%d\n",res); } return 0; }