Happy 2004
Time Limit:1s | Memory limit:32M |
Accepted Submit:142 | Total Submit:279 |
Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004X. 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 20041 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). Output For each test case, in a separate line, please output the result of S modulo 29. Sample Input 1 10000 0 Output for the Sample Input 6 10 Original: 2004 ACM/ICPC Beijing Practice Problem |
解题:
运用到欧拉定理,费马小定理。要求某个数A的所有因子和,首先将该数分解:
先贴代码
int happy(int n)
{
int r,f,t,d;
f=t=d=1;
for (r=0;r<=n;++r)
{
f=f*(r==n?2:4)%29; //f表示2^(2n+1)的值
t=t*3%29; //t表示3^(n+1)的值
d=d*22%29; //d表示167^(n+1)的值
}
r=(f-1)*(t-1)*(d-1)%29; //S=r/332,r的值
return r*9%29; //S%29=r*9%29
}
int main()
{
int n;
while (cin>>n && n!=0)
{
cout<<happy(n%28)<<endl;
}
return 0;
}