G - Happy 2004------(HDU 1452)

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## G - Happy 2004------(HDU 1452)

angel_imp 2016-03-21 17:26:00 浏览803

# Happy 2004

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1346    Accepted Submission(s): 977

Problem 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.

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.

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(n) = (p1^(e1+1)-1)/(p1-1) * (p2^(e2+1)-1)/(p2-1) * ... * (pk^(ek+1)-1)/(pk-1)

167 Mod 29 == 22 所以直接用22就行
((2^(2*x+1)-1)/(2-1) * (3^(x+1)-1)/(3-1) *  (22^(x+1)-1)/(22-1)) Mod 29

1Mod29的逆元 2Mod29的逆元 21Mod29的逆元，这个可以根据扩展欧几里得算法得到，求出之后，我们就进行快速幂 分别求出2^(2x+1)Mod 29 , 3^(x+1)Mod 29,  22^(x+1)Mod 29 的值，然后减一 与 前面所求的逆元进行相乘就ok了

```#include <iostream>

using namespace std;
typedef long long LL;
LL quick_mod(LL a, LL b, LL m)
{
LL ans = 1;
while(b)
{
if(b & 1)
ans = (ans*a)%m;
b>>=1;
a = (a*a)%m;
}
return ans;
}
void exgcd(LL a, LL b, LL &x, LL &y)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
LL x1, y1;
exgcd(b, a%b, x1, y1);
x = y1;
y = x1 - (a/b)*y1;
}
int main()
{
LL n, a, b, c, y, _a, _b, _c;
while(cin>>n,n)
{
exgcd(1,29,_a,y);
exgcd(2,29,_b,y);
exgcd(21,29,_c,y);
_a = (_a+29)%29;
_b = (_b+29)%29;
_c = (_c+29)%29;
///cout<<167%29<<endl;
///cout<<_a<<" "<<_b<<" "<<_c<<endl;
a=(quick_mod(2,2*n+1,29)-1)*_a;
b=(quick_mod(3,n+1,29)-1)*_b;
c=(quick_mod(22,n+1,29)-1)*_c;
cout<<(a*b*c%29)<<endl;
}
return 0;
}
```

angel_imp
+ 关注

corcosa 15214人浏览