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(x)=2004x的因子和F(x)=2004^x的因子和F(x)=2004x的因子和 因为这是个积性函数,则有f(N)=∏i=1nf(qiqi)其中N可以表示为∏i=1nqiqif(N)=\prod_{i=1}^nf(q_i ^{q_i}) 其中 N可以表示为\prod_{i=1}^nq_i ^{q_i}f(N)=∏i=1nf(qiqi)其中N可以表示为∏i=1nqiqi
f(2004n)=f(2(2∗n))∗f(3n)∗f(167n)=(2(2∗n+1)−1)∗(3(n+1)−1)/2∗(167(n+1)−1)/166f(2004 ^ n)= f(2 ^{(2 * n)})* f(3 ^ n)* f(167 ^ n)
=(2 ^{(2 * n + 1)}-1)*(3 ^{(n + 1)}-1)/ 2 *(167 ^{(n + 1)}-1)/ 166f(2004n)=f(2(2∗n))∗f(3n)∗f(167n)=(2(2∗n+1)−1)∗(3(n+1)−1)/2∗(167(n+1)−1)/166
用到乘法逆元:(同余性质)
a ^ k / d = a ^ k *(d-1)d-1即为d的逆元。3的逆元为15 167的逆元为18
JAVA C++ 没区别,最近在JAVA要考试了额,熟悉一下。
import java.util.Scanner;
public class Main {
public static long Q_pow( long a, long p, long mod)
{
long ans = 1%mod;
while(p>0) {
if(p%2==1) ans = ans*a%mod; //防止在对P取模前溢出
a = a*a%mod;
p >>=1; //比除法快多了
}
return ans;
}
public static void main(String[] args) {
int n;
Scanner in = new Scanner(System.in);
while(in.hasNext())
{
n=in.nextInt();
if(n==0) break;
long ans=((Q_pow(167,n+1,29)-1)*18)%29;
ans=(ans*((Q_pow(3,n+1,29)-1)*15)%29)%29;
ans=(ans*(Q_pow(2,2*n+1,29)-1))%29;
System.out.println(ans);
}
in.close();
}
}