http://acm.hdu.edu.cn/showproblem.php?pid=1452
原来真心没见过这种题，不会做，非常帅
gcd(a,b)==1 && s(a,b)==s(a)*s(b)满足这种条件的s叫做积性函数，本题求的因子和就是一个积性函数
接着有一个结论
if(prime[p])s(p^n)=1+p^1+p^2+p^n=(p^(n+1)-1)/(p-1)
s(2004^n)=s(2^(2n))*s(3^n)*s(167^n)
其中，167和22关于29同余
所以，s(2004^n)=s(2^(2n))*s(3^n)*s(2^n)
a=s(2^(2n))=(2^(2n+1)-1)
b=s(3^n)=(3^(n+1)-1)/2
c=s(22^n)=(22^(n+1)-1)/21
数太大，每步求余，除法求余的规则是，除以一个数求余的结果和乘以除数的乘法逆元的求余结果相同
求出2和21的乘法逆元这道题就做完了
#include <iostream> #include <cstring> using namespace std ; int qpow(int a,int b) { int ans=1,buff=a ; while(b) { if(b&1)ans=ans*buff%29 ; buff=buff*buff%29 ; b>>=1 ; } return ans ; } int main() { int x ; while(~scanf("%d",&x),x) { int a=(qpow(2,2*x+1)-1)%29 ; int b=(qpow(3,x+1)-1)*(-14)%29 ; int c=(qpow(22,x+1)-1)*(-11)%29 ; printf("%d\n",a*b*c%29) ; } return 0 ; }
扩展欧几里得算法求乘法逆元模板
int Extend_Eulid(int d,int f) { int x1,x2,x3,y1,y2,y3 ; x1=1,x2=0,x3=f,y1=0,y2=1,y3=d ; while(y3 && y3!=1) { int q=x3/y3 ; int t1,t2,t3 ; t1=x1-q*y1,t2=x2-q*y2,t3=x3-q*y3 ; x1=y1,x2=y2,x3=y3 ; y1=t1,y2=t2,y3=t3 ; } if(!y3)return -1 ; return y2 ; }
原文：http://www.cnblogs.com/xiaohongmao/p/3536029.html
