题意：给你一个n，让你求2004^n所有因子(包括1和本身)的和%29.
题解：
s[i]代表i的所有因子之和，那么有以下两个结论
1、当gcd(a,b)=1时，s[a*b]=s[a]*s[b].
2、当p为素数时，s[p^n]=p^0+p^1+……+p^n=(p^(n+1)-1)/(p-1)
知道上面的基本上就OK了
AC代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int N=52; const LL II=29; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); int love(int a,int b) { int ans=1; while(b) { if(b&1) ans=(ans*a)%II; a=(a*a)%II; b=b>>1; } return ans; } int main() { int i,j,n; while(scanf("%d",&n)&&(n)) { int a,b,c; a=(love(2,2*n+1)-1)*1%II; b=(love(3,n+1)-1)*15%II; c=(love(167,n+1)-1)*18%II; //printf("%d %d %d\n",a,b,c); printf("%d\n",(a*b*c)%II); } return 0; }