Description
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.
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.
Input
The 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.
A test case of X = 0 indicates the end of input, and should not be processed.
Output
For each test case, in a separate line, please output the result of S modulo 29.
Sample Input
1
10000
0
Sample Output
6
10
一个数的因子和是一个积性函数
关于积性函数，即F(ab)=F(a)*F(b)，在数论里有很多积性函数
来证明一下：
S(x)表示x的因子和。
如果x可以分成a,b（一定为素数），那么S(x)=S(a)*S(b）。
为什么一定要分成素数呢，因为一个素数的因子之后1和它本身，对于a,b 来说，就是1,a,1,b，那么x=a*b,x的因子只有1，a,，b，x这四个数，
（1+a）*(1+b)=1+a+b+a*b。看明白了么，这就是所谓的一个数的因子和是一个积性函数。
(a*b)/c %M= a%M * b%M * inv(c)
其中inv(c)即满足 (c*inv(c))%M=1的最小整数
a^(b)%c----->a(b%k(c)+k(c))%c (b>=k(c)) 其中k(c)为c的欧拉值。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
LL qpow(int x,int y){
LL b = 1;
for(;y;y>>=1){
if(y&1) b = (b*x)%29;
x=(x*x)%29;
}b--;
return b<0?b+29:b;
}
int main()
{
int x;
while(~scanf("%d",&x)&&x){
LL a = 2*x+1;if(a>28) a%=28,a+=28;
LL b = x+1;if(b>28) b%=28,b+=28;
printf("%d
",qpow(2,a)*qpow(3,b)*qpow(22,b)*9%29);
}
return 0;
}