HDU 1452 Happy 2004 (素因子分解+快速幂模+乘法逆元) - c++编程基础

题意：给你一个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;  
}