2020牛客暑期多校训练营（第四场）

Basic Gcd Problem
思路：答案即为 。

#include<iostream>
typedef long long ll;
using namespace std;
const int mod=1e9+7;
int main(){
    int t,c,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&c);
        ll ans=1;
        for(int i=2;i*i<=n;i++)//筛选出所有素数
            while(n%i==0){
                n/=i;
                ans=ans*c%mod;
            }
        if(n>1)  ans=ans*c%mod;//可能i是n的质因数，但当n不断除以素数，会导致 
                                //i*i>n
        printf("%lld\n",ans);
    }
    return 0;
}