LightOJ – Necklace

L
Problem NameNecklace
JudgeLightOJ
Problem Linkhttps://lightoj.com/problem/necklace
Algorithms & DSGCD, Extended GCD, Binary Exponentiation, Modular Inverse
#include<bits/stdc++.h> using namespace std; typedef long long ll; constexpr ll MOD = 1e9+7; constexpr ll MX = 1005; ll exGCD(ll a, ll b, ll &x, ll &y) { if(b==0) { x=1; y=0; return a; } ll x1,y1; ll d=exGCD(b,a%b,x1,y1); x=y1; y=x1-(a/b)*y1; return d; } ll modInv(ll a, ll mod) { ll x, y; ll g=exGCD(a,mod,x,y); if(g!=1) return -1; //No Solution x=(x%mod+mod)%mod; return x; } 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 gcd(ll a, ll b) { while(b) { a%=b; swap(a,b); } return a; } int main() { ll t; cin>>t; ll n, k; for(ll T=1; T<=t; T++) { cin>>n>>k; ll inv_n=modInv(n,MOD); ll ans=0; for(ll d=1; d<=n; d++) { ll tmp_ans=binpow(k,gcd(n,d),MOD); ans=((ans%MOD)+(tmp_ans%MOD))%MOD; } ans=((ans%MOD)*(inv_n%MOD))%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 !!