CF #589 (Div. 2)C. Primes and Multiplication 快速幂+质因数

开始想出来了一个容斥的做法，但是一直WA，后来换了一种统计方式就对了. 

#include <bits/stdc++.h>
#define mod 1000000007 
#define ll unsigned long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;    
vector<ll>v;    
ll qpow(ll base,ll k) 
{
    ll tmp=1ll; 
    for(;k;k>>=1,base=base*base%mod) if(k&1) tmp=tmp*base%mod; 
    return tmp;    
}
int main() 
{
    int i,j; 
    ll x,n,p;   
    // setIO("input"); 
    scanf("%lld%lld",&x,&n);   
    p=x;   
    for(i=2;i*i<=p;++i) 
    {
        if(p%i==0) 
        {
            v.push_back(i);   
            for(;p%i==0;) p/=i;   
        }
    }
    if(p>1) v.push_back(p);    
    ll ans=1ll; 
    for(i=0;i<v.size();++i) 
    {
        ll m=n;   
        ll now=0; 
        while(m>=v[i]) 
        {
            now+=m/v[i];
            m/=v[i]; 
        }   
        ans=ans*qpow(v[i], now)%mod;  
    } 
    printf("%lld\n",(long long)ans);     
    return 0; 
}