题目大意：定义一个函数如下：
$f_c(x)=max_{i-1cdots x-1}c imes f_c(gcd(i,x)),x>1$
$f_c(1)=1,x=1$
给你T组数据，每组给出n,c，让你求$f_c(n)$的值对1e9+7取余，$n,c<=1e6,T<=1e6$
输入
2 3 3 10 5
输出
3 25
emmmm,对于任意一个数s，他可以表示成$s=p_1^{k_1}p_2^{k_2}cdots p_m^{k_m}$那么他就可以递归到$s=p_1^{k_1}p_2^{k_2}cdots p_m^{k_m-1}$然后一层层递归下去知道0次方，也就是说我们直接计算$nb=k_1+k_2+cdots k_m$的值就OK了，然后用快速幂计算一下$c^{nb}$就可以了。
但我们要先预处理一下每个数的素因子的和值，这个就不多说了，很容易懂。
以下是AC代码：
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int mod=1e9+7; const int mac=1e6+10; int vis[mac]; int prim[mac],c; int sb[mac]; ll qpow(ll a,ll b) { ll ans=1; while (b){ if (b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main(int argc, char const *argv[]) { int t; scanf ("%d",&t); for (int i=2; i<sqrt(mac); i++) if (!vis[i]) for (int j=i*i; j<mac; j+=i) vis[j]=1; int cnt=0; for (int i=2; i<mac; i++) if (!vis[i]) prim[++cnt]=i; for (int i=2; i<mac; i++){ if (!vis[i]) sb[i]=1; int p=i; for (int j=1; j<cnt; j++){ while (p%prim[j]==0) sb[i]++,p/=prim[j]; if (!vis[p]){ if (p>1) sb[i]++; break; } } } while (t--){ int n; scanf ("%d%d",&n,&c); ll ans=1; if (!vis[n] && n>1) ans=ans*c%mod; else if (vis[n]){ ans=qpow(c,sb[n]); } printf("%lld ",ans); } return 0; }