Primes and Multiplication

​​C - Primes and Multiplication​​

思路：找到​

​x​

​​的所有質數因子，用一個​

​vector​

​儲存起來，然後對于每一個質因子來說，我們要找到它對最後的答案的貢獻的大小，即要找到它在最後的乘積中出現了多少次。

求解方法：

for(auto i:v)

{

ll cnt=0;

ll temp=n/i;

while(temp)

cnt+=temp,temp/=i;

ans=(ans*qpow(i,cnt))%mod;

}

另外，該題還需要用到快速幂的技巧。

ll qpow(ll x,ll n)

{

ll re=1;

while(n)

{

if(n&1) re=(re*x)%mod;

n>>=1,x=(x*x)%mod;

}

return re;

}

代碼：

// Created by CAD on 2019/10/1.
#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int mod=1e9+7;

ll qpow(ll x,ll n)
{
    ll re=1;
    while(n)
    {
        if(n&1) re=(re*x)%mod;
        n>>=1,x=(x*x)%mod;
    }
    return re;
}
vector<ll> v;
int main()
{
    ll n,x;    cin>>x>>n;
    for(ll i=2;i*i<=x;++i)
        if(x%i==0)
        {
            v.push_back(i);
            while(x%i==0)
                x/=i;
        }
    if(x!=1) v.push_back(x);
    ll ans=1;
    for(auto i:v)
    {
        ll cnt=0;
        ll temp=n/i;
        while(temp)
            cnt+=temp,temp/=i;
        ans=(ans*qpow(i,cnt))%mod;
    }
    cout<<ans<<endl;
}