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

题目大意：

求 2004^X的所有因子的和模上29的值；

解题思路：

首先根据算术基本定理（1），

若 n 的标准素因子分解表达式为 n = p1^e1 * p2^e2 * …… * pk^ek

设f(n) 为n 的所有因子之和，则有:

f(n) = (p1^(e1+1)-1)/(p1-1) * (p2^(e2+1)-1)/(p2-1) * ... * (pk^(ek+1)-1)/(pk-1)

因为2004 = 2^2 * 3 * 167，所以2004^x也肯定是2^(2*x) * 3^x * 167^x;

然后根据算术基本定理：

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

设a = (2^(2*x+1)-1)/1;

设b = (3^(x+1)-1)/2 ;

设c = (22^(x+1)-1)/21);

我们只要分别求出 a Mod 29, b Mod 29, c Mod 29的值就行啦，因为他们带着除数所以我们进行求解逆元,分别是

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

最后输出的就是 a*b*c Mod 29，下面是详细代码：

#include 
     
      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<