Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004^X. Your job is to determine S modulo 29 (the rest of the d ...
Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004^X. Your job is to determine S modulo 29 (the rest of the division of S by 29).
Take X = 1 for an example. The positive integer divisors of 2004^1 are 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 and 2004. Therefore S = 4704 and S modulo 29 is equal to 6.
InputThe input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000).
A test case of X = 0 indicates the end of input, and should not be processed.
OutputFor each test case, in a separate line, please output the result of S modulo 29.
Sample Input
1 10000 0
Sample Output
6 10
唯一分解定理：
一個整數A一定能被分成：A=(P1^K1)*(P2^K2)*(P3^K3).....*(Pn^Kn)的形式。其中Pn為素數。
約數和公式
對於一個已經被分解的整數A=(P1^K1)*(P2^K2)*(P3^K3).....*(Pn^Kn),有約數和S=(1+P12+P13+.....P1k1)*.....(1+Pn2+Pn3+.....Pnkn)。
等比數列求和公式
SUM=P1(1- P1^n)/(1-P1)=P1(P1^n -1)/(P1-1)
S=SUM1+SUM2+......+SUMn
對於此題ans=2^(2n+1)-1+(3^(n+1)-1)/2+(167^(n-1)-1)/166
乘法逆元：
如果ax≡1 (mod p),且gcd(a,p)=1（a與p互質），則稱a關於模p的乘法逆元為x。
擴展歐幾裡得在這裡就不多說了。這裡說一下費馬小定理：
假如a是整數，p為素數，則a^p-a為p的倍數。 由此可得a^p - a=1 mod p =>a^p=a mod p =>a^(p-1) =1 mod p，結合逆元的定義，a*x=1 mod p。則逆元x=a^(p-2) mod p。
取模不可用除法，所以ans*乘法逆元，剩下的就是求出逆元可解。乘法逆元可由擴展歐幾裡得演算法求得，也可有費馬小定理求得。
歐拉定理求逆元：a^(phi(m)-1);
代碼如下：
#include<iostream>
#include<cstdio>
#define LL long long
#define mod 29
using namespace std;
LL pow(LL a,LL n)
{
LL base=a,ret=1;
while(n)
{
if(n&1) ret=(ret*base)%mod;
base=(base*base)%mod;
n>>=1;
}
return ret%mod;
}
int main()
{
LL T,x;
while(~scanf("%lld",&x),x)
{
LL rev=pow(13,27);//逆元
LL res=(pow(2,2*x+1)-1)*(pow(3,x+1)-1)*(pow(22,x+1)-1);
printf("%lld\n",res*rev%mod);
}
}
