地址：https://ac.nowcoder.com/acm/contest/5669/B
解析：
题意如此，主要是要先看懂这个公式。
由于是每次都是c*c*c...所以不用看c了，直接分解n
要想max最大，很明显需要尽量多次得分解n，那么每次找n的最大因子x，gcd(n,x)
举几个例子，计算方式根据上一句：
看一下分别都乘几次c
18->9->3->1 2*3^2 1+2=3
21->7->1 3*7 1+1=2
27->9->3->1 3^3 3
有结论，c乘多少次，取决于n的质因子有几个，所以边分解边乘即可：
#include<iostream> #include<cstring> #include<string.h> #include<cmath> using namespace std; typedef long long ll; const int maxn=1e6+10; const int mod=1e9+7; int a[maxn]; int qk(ll a, ll b,ll c) { ll ans=1; a=a%c; while(b) { if(b%2==1) ans=(ans*a)%c; b=b/2; a=(a*a)%c; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n,c; //ll会超时 scanf("%d%d",&n,&c); int cnt=0; ll sum=1; for(int i=2;i*i<=n;i++) { while(n%i==0) { n=n/i; sum=(sum%mod*c%mod)%mod; } } if(n!=1) sum=(sum*c)%mod; printf("%lld ",sum); }