LightOJ – Efficient Pseudo Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr ll mod = 1000000007;

vector<ll>PF;
map<ll,ll>factCt;
void PrimeFactCt(ll n) {
    PF.clear();
    factCt.clear();
    if (n%2==0) {
        PF.push_back(2);
        while (n % 2 == 0) {
            factCt[2]++;
            n /= 2;
        }
    }
    for (ll i=3; i*i<=n;i+= 2) {
        if (n%i==0) {
    		ll tmp_pf=i%mod;
        	if(!factCt[tmp_pf]){
            	PF.push_back(tmp_pf);
        	}
       	 	while (n%i==0) {
            	factCt[tmp_pf]++;
            	n/=i;
        	}
        }
    }
    if (n>1) {
        if (!factCt[n]) PF.push_back(n%mod);
        factCt[n%mod]++;
    }
}

ll binpow(ll base, ll power, ll mod)
{
    base%=mod;
    power=power%(mod-1);
    ll result=1;
    while(power>0){
        if(power&1)result=(result*base)%mod;
        base=(base*base)%mod;
        power>>=1;
    }
    return result;
}

ll modInv(ll a, ll mod) {
    return binpow(a, mod-2, mod);
}

int main()
{
    ll t;
    cin>>t;
    ll n, m;
    for(ll T=1;T<=t;T++){
        cin>>n>>m;
        PrimeFactCt(n);
        ll ans=1;
        for(ll i=0;i<(ll)PF.size();i++){
            ll pow=(factCt[PF[i]]*m)+1;
            ll down=modInv(PF[i]-1,mod);
            if(down<0){
                down+=mod;
                down%=mod;
            }
            ll up=binpow(PF[i],pow,mod);
            up=(up-1+mod)%mod;
            ll tmp_ans=(up*down)%mod;
            ans=((ans%mod)*tmp_ans)%mod;
        }
        cout<<"Case "<<T<<": ";
        cout<<ans<<"\n";
    }
    return 0;
}
Code language: PHP (php)