题目来源;https://ac.nowcoder.com/acm/contest/5669/B
题意:求
思路:代入数值计算得出最后的答案一定是输出的n的幂,然后就是确定这个幂的指数,先预处理出所有数的最大因子
(1)只要这个最大因子不是 1,指数就要加 1;
(2)接着找这个最大因子的最大因子是不是1 ,不是 1 的话继续上面的操作;如果最大因子是1的话就输出答案:(就是个迭代)
#include<bits/stdc++.h> using namespace std; const int N = 1e6+1; const int mod = 1e9+1; int f[N]; int pri[N],cnt; int vis[N]; void init() { f[1] = 1; for (int i = 2; i < N; i++) { if (!vis[i]) { pri[cnt++] = i; f[i] = 1; } for (int j = 0; j < cnt && i * pri[j] < N; j++) { f[i * pri[j]] = max(f[i * pri[j]],i); vis[i * pri[j]] = 1; if (i % pri[j] == 0) break; } } } int qpow(int a,int b) { int res=1; while(b) { if(b&1) res=1ll*res*a%mod; a=1ll*a*a%mod; b >>= 1; } return res; } int main() { int q; init(); cin>>q; while(q--) { int x,y; cin>>x>>y; if(x==1) { cout << 1 << endl; } else{ int tmp=f[x]; int cnt=1; while(tmp!=1) { tmp=f[tmp]; cnt++; } cout<<qpow(y,cnt)%mod<<endl; } } return 0; }