这题.....简直没话可说
首先需要利用欧拉定理优化指数 防止快速幂爆精度
然后需要注意 每次使用的欧拉函数大小都不一样
最后输出的时候补0....
然后特判 指数小于phi(m)的数不能约 要单独算(或者叫打表?)
Code:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 300000; ll b,n,p,tot,num[10],cnt,ans,f[110][110]; int prime[1000010],phi[10000010]; bool vis[10000010]; ll qpow(ll a,ll b,ll mod) { ll res = 1; while(b) { if (b & 1) res = (res * a) % mod; b >>= 1; a = (a * a) % mod; } return res; } void init() { phi[1] = 1; phi[10000000] = 4000000; phi[4000000] = 1600000; phi[1600000] = 640000; phi[640000] = 256000; for (int i = 2; i <= maxn; i++) { if (!vis[i]) { prime[++tot] = i; phi[i] = i - 1; } for (int j = 1; j <= tot; j++) { ll t = prime[j] * i; if (t > maxn) break; vis[t] = 1; if (i % prime[j] == 0) { phi[t] = phi[i] * prime[j]; break; } phi[t] = phi[i] * (prime[j] - 1); } } } ll solve(ll dep,ll mod) { if (dep == 1) return b; if (mod == 1) return 0; if (f[b][dep] == -1) { ll temp = phi[mod]; ll tt,temp2 = solve(dep - 1,temp); tt = qpow(b,temp2 + temp,mod); return f[b][dep] = tt; } return f[b][dep] % mod; } int main() { memset(f,-1,sizeof(f)); init(); while (~scanf("%lld",&b) && b) { cnt = 0; memset(num,0,sizeof(num)); scanf("%lld%lld",&n,&p); if (p == 0) printf("0 "); else { ll cur = p; p = qpow(10,p,100000010); if (f[b][n] != -1) ans = f[b][n]; else { if (n == 2 && b <= 6) ans = qpow(b,b,10000000); else if (n == 3 && b <= 3) ans = qpow(b,qpow(b,b,10000000),10000000); else if (n == 4 && b == 2) ans = qpow(b,qpow(b,qpow(b,b,10000000),10000000),10000000); else ans = solve(n,10000000); f[b][n] = ans; } while (ans) { num[++cnt] = ans % 10; ans /= 10; } for (int i = cur; i >= 1; i--) printf("%d",num[i]); printf(" "); } } return 0; }