当前位置 : 主页 > 网页制作 > css >

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

来源:互联网 收集:自由互联 发布时间:2021-06-13
开始想出来了一个容斥的做法,但是一直WA,后来换了一种统计方式就对了. #include bits/stdc++.h#define mod 1000000007 #define ll unsigned long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; v

开始想出来了一个容斥的做法,但是一直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; 
}
网友评论