Basic Gcd Problem

题目链接：https://ac.nowcoder.com/acm/contest/5669/B
解题思路：
我们可以直接看出当x每次都只去掉一个质因子，fc=c^(x的素因子个数)，本题T是1e6因此直接欧拉筛打表好了，维护一下素因子个数。
代码：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int MAXN = 1e6+7;
typedef long long ll;
ll quick_pow(ll a, ll b, ll m){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1; 
    } 
    return ans;
}
int prime[MAXN], cnt;
bool vis[MAXN];
int fac[MAXN];
void Prime()
{
    for(int i = 2; i <= MAXN; i++) {
        if(!vis[i]) {
            prime[++cnt] = i; fac[i] = 1;
        }
        for(int j = 1; j <= cnt&&i * prime[j] <= MAXN; j++) {
            vis[i * prime[j]] = 1;
            fac[i * prime[j]] = fac[i] + 1;    
            if(i % prime[j] == 0) break;    //当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。 
        }
    }
}
int main()
{
    int t;
    Prime();
    scanf("%d",&t);
    while(t--)
    {
        ll n, c;
        scanf("%lld%lld",&n,&c);
        printf("%lld\n",quick_pow(c,fac[n],mod));
    }
}