2016-08-30

HDU 5728 PowMod【欧拉函数】

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5728

题意：

设$k=\sum_{i=1}^{m} \varphi (i\times n)\ mod\ 1000000007$，其中$n$无平方数因子，求$ans=k^{k^{k^{k^{…^k}}}}(\ mod \ p)$，其中$k$无穷多个，$1 \leq n, m, p \leq 10^{7}$

分析：

无穷次幂的处理见bzoj 3884
然后是化简式子，由于$n$无平方数因子，设$p$为$n$的质因子，则$gcd(p, {n \over p}) = 1$
利用到欧拉函数的两条性质：

$若gcd(m,n)=1，则\phi(mn)=\phi(m)\phi(n)$【积性函数性质】
$若i\ mod\ p = 0, 那么 \phi(i \times p)=\phi(i)\times p$【利用$若gcd(a,b)=1,则gcd(a+b,b)=1$】

设$f(n,m)=\sum_{i=1}^m\phi(i\times n)$，那么，
$f(n,m)=\sum_{i=1}^m\phi(i\times n)$
$=\sum_{i=1且p\mid i}^m\phi(i\times \frac{n}{p}\times p)+\sum_{i=1且p\nmid i }^{m}\phi(i\times \frac{n}{p}\times p)$
$=\phi(p)\sum_{i=1且p\mid i}^m\phi(i\times \frac{n}{p})+p\sum_{i=1且p\nmid i}^{m}\phi(i\times \frac{n}{p})$
$=\phi(p)\sum_{i=1且p\mid i}^m\phi(i\times \frac{n}{p})+(\phi(p)+1)\sum_{i=1且p\nmid i}^{m}\phi(i\times \frac{n}{p})$
$=\phi(p)\sum_{i=1且p\mid i}^m\phi(i\times \frac{n}{p})+\sum_{i=1且p\nmid i}^{m}\phi(i\times \frac{n}{p})$
$=\phi(p)\sum_{i=1}^m\phi(i\times \frac{n}{p})+\sum_{i=1}^{\frac{m}{p}}\phi(i\times n)$
$=\phi(p)f(\frac{n}{p},m)+f(n,\frac{m}{p})$
依次递归下去即可，处理类似记忆化搜索，最终最多遍历$n$的所有质因数。

代码：

/*************************************************************************
    > File Name: 5728.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/30 9:52:29
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 1e7 + 5, mod = 1e9 + 7;
int phi[maxn], prime[maxn], sum[maxn];
int tot; 
map<pii, int> F;
void init()
{
    phi[1] = 1;
	tot = 0;
    for(int i = 2; i < maxn; ++i){
        if(!phi[i]){
            phi[i] = i - 1;
            prime[tot++] = i;
        }
        for(int j = 0; j < tot && i * 1ll * prime[j] < maxn; ++j){
            if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            else{
                phi[i * prime[j] ] = phi[i] * prime[j];
                break;
            }
        }
    }
	sum[0] = 0;
	for(int i = 0; i < maxn; i++){
		sum[i] = (sum[i - 1] + phi[i]) % mod;
	}
}
int quick_pow(int b, int a, int p)
{
	int res = 1;
	for(; a; a >>= 1, b = b * 1ll * b % p){
		if(a & 1) res = res * 1ll * b % p;
	}
	return res;
} 
int k;
int dfs(int p)
{
	if(p == 1) return 0;
	if(k == 1) return 1;
	return quick_pow(k, dfs(phi[p]) + phi[p], p);
}
vector<int>ans;
int dfs2(int n, int m, int t)
{
	if(F[pii(n, m)]) return F[pii(n, m)];
	if(n == 1) return sum[m];
	if(m == 1) return phi[n];
	if(m == 0) return 0;
	int num = ans[t];
	return F[pii(n, m)] = (phi[num] * 1ll * dfs2(n / num, m, t - 1) % mod + dfs2(n, m / num, t)) % mod;
}
int main (void)
{
	int n, m, p;
	init();
	while(~scanf("%d%d%d", &n, &m, &p)){
		ans.clear();
		int tmp = n;
		for(int i = 0; i < tot; i++){
			if(tmp % prime[i] == 0){
				while(tmp % prime[i] == 0){
					ans.push_back(prime[i]);
					tmp /= prime[i];
				}
			}
			if(tmp == 1) break;
		}
		k = dfs2(n, m, ans.size() - 1);
		printf("%d\n", dfs(p));
	}
	return 0;
}