PowMod
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1008 Accepted Submission(s): 341
Problem Description
Declare:
k=∑mi=1φ(i∗n) mod 1000000007
k=∑mi=1φ(i∗n) mod 1000000007
n is a square-free number.
φ is the Euler's totient function.
find:
ans=kkkk...k mod p
There are infinite number of k
Input
Multiple test cases(test cases ≤100), one line per case.
Each line contains three integers, n,m and p.
1≤n,m,p≤107
Output
For each case, output a single line with one integer, ans.
Sample Input
1 2 6
1 100 9
1 100 9
Sample Output
4
7
7
Author
HIT
Source
题意：
令K = sigma(phi(i * n)) 1 <= i <= m
求K的超级幂。
题解： 关于下面要用到的欧拉函数的几个证明。
1、首先显然phi(p) = p-1, phi(1) = 1
2、若 n = p^k，则 phi(n) = p^k - p^(k-1)
证明：显然不互质的有p,2p,......,(p^(k-1)-1)*p，以及p^k
所以共有p^(k-1)个
3、若 n = a * b, gcd(a, b) == 1， 则phi(n) = phi(a) * phi(b)
证明：
phi(a)个与a互质的数，设它们为A1,A2......Aphi(a)
同理，我们也有B1,B2,.....,Bphi(b)为与b互质的数。
那么与n互质的数为Ai*b+Bj*a，共有phi(a)*phi(b)个。
我们来考察Ai*b+Bj*a的性质。
我们要证明两点：
1、Ai*b+Bj*a与n互质
2、除了这些数，没有与n互质的数了。
第一点、如果有gcd(a*Bi+b*Ai,a*b)=x>1
那么x|a*b，又gcd(a,b)=1，所以必有x|a或者x|b且不同时成立。
不妨假设x|a，那么a*Bi/x是个整数，而gcd(Ai,a)=1，所以gcd(Ai,x)=gcd(b,x)=1，
喜爱内燃此时b*Ai/x不为整数，与x为最大公约数的假设矛盾。
第二条、这是显然的。。。如果有gcd(x,a*b)!=1，那么gcd(x,a)!=1和gcd(x,b)!=1至少有一条成立。
所以证毕。
4、若n=p1^k1*p2&k2*.....*pm^km，那么
phi(n)=n*(1-1/p1)*(1-1/p2)*.....*(1-1/pm)
5、当n>2时，phi(n)是偶数，因为1-1/p=（p-1）/p，p-1必然是偶数。 K = sigma(phi(i * n)) % Q, Q = 1e9+7, 1 <= i <= m
= sigma(phi( (i * n) / p * p )), p|n
= sigma(phi( i * n / p * p)), i % p != 0 + sigma(phi( i * n * p)), 1 <= i <= floor(m / p) % Q
= sigma(phi( i * n / p) * phi(p)), i%p != 0 + sigma(phi(i * (n/p) * p^2)), 1 <= i <= floor(m / p), %Q
= phi(p) * sigma(phi(i * n / p)), i%p != 0 + sigma(phi(i * (n / p)) * phi(p^2)), 1 <= i <= floor(m/p) %Q
= phi(p) * sigma(phi(i * n / p)) , i % p != 0 + sigma(phi(i * (n / p)) * p * phi(p)), 1 <= i <= floor(m/p) %Q
= phi(p) * sigma(phi(i * n / p)) , i % p != 0 + sigma(phi(i * (n / p)) * (phi(p) + 1) * phi(p)), 1 <= i <= floor(m/p) %Q
= phi(p) * ( sigma(phi(i * n / p)), i % p != 0 + sigma(phi(i * n)), 1<=i<=floor(m/p) ) + sigma(phi(i * n)), 1<=i<=floor(m/p) %Q
= phi(p) * sigma(phi(i * (n / p))), 1 <= i <= m + sigma(phi(i * n)), 1 <= i <= floor(m / p)
令F(m,n) = sigma(phi(i * n)) % Q,
根据上述证明，有当p|n时，
F(m, n) = phi(p) * F(m, n / p) + F(floor(m / p), n) %Q
所以可以递归计算F(m, n)， 这一步复杂度为O（（number of P）^2） 当算出K值后，需要计算它的超级幂。
有A^B mod C = A^(B % phi(C) + phi(C)) % C
这个证明我不会，网上有证明，但因为年代久远，百度博客搬迁，原地址没了。。。
（实际上这个的作用除了计算超级幂好像没什么用。。。。（这只是弱鸡的视野
事实上，这里的A跟B是一个东西，而phi(C)是不断减少的，只有phi(1)==1，
而且收敛速度很快。
所以不断递归就好啦。
const int N = , MOD = 1e9 + ;
int prime[N], tot;
bool notPrime[N];
int phi[N], sumphi[N]; int n, m, p;
int factor[N], totFactor; inline int add(int x, int y, int MOD = MOD) {
return ((x + y) % MOD + MOD) % MOD;
} inline int mul(int x, int y, int MOD = MOD) {
return ((x * 1ll * y) % MOD + MOD) % MOD;
} inline void getPrime() {
phi[] = , sumphi[] = ;
for(int i = ; i < N; ++i) {
if(!notPrime[i]) prime[tot++] = i, phi[i] = i - ;
for(int j = ; j < tot; ++j) {
if(i * prime[j] >= N) break;
notPrime[i * prime[j]] = true;
if(i % prime[j]) phi[i * prime[j]] = phi[i] * phi[prime[j]];
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
sumphi[i] = add(phi[i], sumphi[i - ]);
}
} inline void getFactor(int x) {
totFactor = ;
for(int i = ; i < tot; ++i)
if(!(x % prime[i])) {
factor[totFactor++] = prime[i];
x /= prime[i];
if(x <= ) break;
}
} inline int f(int index, int m, int n) {
if(index >= totFactor || n == ) return sumphi[m]; // n == 1
if(m <= ) return ;
int part1 = f(index + , m, n / factor[index]),
part2 = f(index, m / factor[index], n);
return add(mul(phi[factor[index]], part1), part2);
} inline int fastpow(int basic, int times, int p) {
int ret = ;
while(times) {
if(times & ) ret = mul(ret, basic, p);
basic = mul(basic, basic, p), times >>= ;
}
return ret;
} inline int superPower(int k, int p) {
/**
* 1. k^X mod p = k^(X mod phi(p) + phi(p)) mod p X = k^k^k.....
* 2. fastpow(x, y, z) x^y mod z
* */
if(p == ) return ;
int powers = superPower(k, phi[p]) + phi[p];
return fastpow(k, powers, p);
} inline void solve() {
getFactor(n);
int k = f(, m, n);
int ans = superPower(k, p);
printf("%d\n", ans);
} int main() {
getPrime();
while(scanf("%d%d%d", &n, &m, &p) == ) solve();
return ;
}