HDU2837 (Calculation)[指数循环节，欧拉函数]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2837

指数循环节对应公式：a^(b%phi(p)+phi(p))≡a^b (mod p) (b>=phi(p))
递归求解每个n即可，需要注意的是公式对应条件b>=phi(p)，如果不满足条件，则不能套公式（即不用多加一个phi(p)），这里在pow_pow里特殊处理了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll euler_phi(ll n) {
	ll m=(ll)sqrt(n+0.5);
	ll ans=n;
	for(int i=2;i<=m;i++) if(n%i==0) {
		ans=ans/i * (i-1);
		while(n%i==0) n/=i;
	}
	if(n>1) ans=ans/n*(n-1);
	return ans;
}
ll pow_mod(ll x,ll y,ll m) {
	ll ans=1;
	bool flag=false;
	if(x>=m) flag=true;
	x%=m;
	for(;y;y>>=1) {
		if(y&1) {
			if(ans*x>=m) flag=true;
			ans=(ans*x)%m;
		}
		if((y>>1) && (x*x>=m)) flag=true; 
		x=(x*x)%m;
	}
	if(flag) return ans+m;
	return ans;
}
ll f(ll n,ll m) {
	if(n==0) return 1;
	if(n<10) {
		if(n>=m) return n%m+m;
		else return n;
	}
	ll phi=euler_phi(m);
	ll tmp=f(n/10,phi);
	ll ans=pow_mod(n%10,tmp,m);
	return ans;
}
int main() {
	int T;
	int n,m;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&m);
		printf("%lld\n",f(n,m)%m);
	}
}