hdu 1452 Happy 2004 (快速幂+取模乘法逆元）

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

题意：找2014^x%29的值。

快速幂和取模乘法逆元。乘法逆元：x=(1/b)%m. 求x的值。x*b=k*m+1,即k去最小正整数时，x也为整数。即b能被k*m+1整除。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int f1(int x,int y)
 5 {
 6     int ans=1;
 7     while (y)
 8     {
 9         if (y&1) ans=ans*x%29;
10         x=x*x%29;
11         y>>=1;
12     }
13     return ans;
14 }
15 int f2(int x)
16 {
17     int i=1;
18     while (i)
19     {
20         if ((29*i+1)%x==0) break;
21         i++;
22     }
23     return (29*i+1)/x;
24 }
25 int main()
26 {
27     int x,a,b,c;
28     while (~scanf("%d",&x))
29     {
30         if (!x) break;
31         a=(f1(2,2*x+1)-1)%29;
32         c=(((f1(3,x+1)-1)%29)*f2(2))%29;
33         b=(((f1(22,x+1)-1)%29)*f2(21))%29;
34         printf("%d
",(a*b*c)%29);
35     }
36     return 0;
37 }