LightOJ – Efficient Pseudo Code

L
Problem NameEfficient Pseudo Code
JudgeLightOJ
Problem Linkhttps://lightoj.com/problem/efficient-pseudo-code
Algorithms & DSPrime Factorization, Modular Arithmetics, Big Mod. Mod Inverse
#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)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!