Hdu1452Happy 2004费马小定理推除法逆元+同余定理+积性函数

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.

InputThe 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.
OutputFor each test case, in a separate line, please output the result of S modulo 29.

Sample Input

1
10000
0

Sample Output

6
10



同余定理:a*b%c=((a%c)*(b%c))%c 或者可以=a%c*b%c
　　　　(a-b)%c=a%c-b%c,但是需要注意的是，如果计算出来为负数，需要加上出来c*1

 1 #include<stdio.h>
 2 typedef long long ll;
 3 
 4 const int mod=29;
 5 int ksm(int x,int n)
 6 {
 7     int res=1;
 8     while(n>0)
 9     {
10         if(n&1)
11             res=res*x%mod;
12         x=x*x%mod;
13         n>>=1;
14     }
15     return res;
16 }
17 
18 int main()
19 {
20     int x;
21     int k2=ksm(2,27);
22     int k166=ksm(166,27);
23 
24     while(~scanf("%d",&x)&&x)
25     {
26         int k3=ksm(3,x+1);
27         if(k3-1<0)
28             k3=k3-1+29;
29         else
30             k3--;
31             
32         int k167=ksm(167,x+1);
33         if(k167-1<0)
34             k167=k167-1+29;
35         else
36             k167--;
37 
38         int s2=ksm(2,2*x+1);
39         if(s2-1<0)
40             s2=s2-1+29;
41         else
42             s2--;
43             
44         int s3=k2*k3%29;
45         int s167=k167*k166%29;
46         int sum=s2*s3*s167;
47         printf("%d\n",sum%29);
48     }
49     return 0;
50 }