HDU 1452 Happy 2004 (素因子分解+快速冪模+乘法逆元)

題意：給你一個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 <iostream>   
#include <vector>   
#include <list>   
#include <deque>   
#include <queue>   
#include <iterator>   
#include <stack>   
#include <map>   
#include <set>   
#include <algorithm>   
#include <cctype>   
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <string>   
#include <cmath>   
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;  
}