Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
ncr
//https://comeoncodeon.wordpress.com/2011/07/31/combination/ #include <bits/stdc++.h> using namespace std; typedef long long int ll; // inverse modulo ll im(ll a, ll b){ ll x=0, y=1, r, q, ta=a; while(b){ r=a%b; q=a/b; a=b; b=r; r=x; x=y; y=r-q*y; } x+=ta; return x%ta; } // power mod ll pm(ll a, ll e, ll m){ ll r=1; while(e){ if(e&1) r=r*a%m; e>>=1; a=a*a%m; } return r; } // factor m into powers of prime void pfp(int m, vector<pair<int,int> > &pf){ for(int i=2; i*i<=m; i++){ int cnt=0; while(m%i==0){ cnt++; m/=i; } if(cnt) pf.push_back(make_pair(i,cnt)); } if(m>1) pf.push_back(make_pair(m,1)); } // chinese remainder theorem ll cr(int m, vector<pair<int,int> >&cpf){ ll ans=0; for(auto pr : cpf){ ll mi=m/pr.first; ll bi=im(pr.first,mi%pr.first); ans+=((mi*bi%m)*pr.second)%m; } return ans%m; } void nb(ll n, int b, vector<int> &br){ int i=0; while(n){ br[i++]=n%b; n/=b; } } void NB(vector<int> &ni, vector<int> &Xi, int p, int e){ for(int j=0; j<Xi.size(); j++){ unsigned long long int r=1; for(int i=j; i<ni.size() && i<j+e; i++, r*=p){ Xi[j]+=ni[i]*r; } } } // carry void cry(vector<int> &ni, vector<int> &mi, vector<int> &ei){ for(int i=0; i<ni.size(); i++){ int cnt=0; for(int j=i; j<ni.size(); j++){ cnt+=(ni[j]<mi[j]); } ei[i]=cnt; } } // ncr%p^e ll ncrm(ll n, ll r, pair<int,int> pf){ vector<int> ni(64,0), ri(64,0), mi(64,0); vector<int> Ni(64,0), Ri(64, 0), Mi(64,0); vector<int> ei(64,0); nb(n,pf.first,ni); nb(r,pf.first,ri); nb(n-r,pf.first,mi); NB(ni,Ni,pf.first,pf.second); NB(ri,Ri,pf.first,pf.second); NB(mi,Mi,pf.first,pf.second); if(r>n/2) cry(ni,ri,ei); else cry(ni,mi,ei); int np=pow(pf.first,pf.second); vector<ll> v(np+1, 1); for(int i=1; i<=np; i++){ v[i]=v[i-1]; if(i%pf.first!=0) v[i]=v[i]*i%np; } ll ans=1; for(int i=0; i<Ni.size(); i++){ ans=ans*v[Ni[i]]%np; ans=ans*im(np,v[Ri[i]])%np; ans=ans*im(np,v[Mi[i]])%np; } ans=ans*pm(pf.first,ei[0],np)%np; if(pf.first==2 && pf.second>=3) return ans; if(ei[pf.second-1]&1) return (np-ans)%np; return ans; } int main(){ int t; scanf("%d",&t); while(t--){ ll n, k; int m; scanf("%lld %lld %d",&n,&k,&m); vector<pair<int,int> > vpf; vector<pair<int,int> > rpf; pfp(m,vpf); ll q=n/k; ll r=n%k; if(r>0) r=k-r+1; else{ q--; r=1; } n=q+r-1; k=q; for(auto xy : vpf){ ll p1=ncrm(n,k,xy), p2=pow(xy.first,xy.second); rpf.push_back(make_pair(p2,p1)); } printf("%lld %lld\n",q+1,cr(m,rpf)); } }
run
|
edit
|
history
|
help
0
Array Subset of another array
CharSearch
multimap
Different Subarray Sum Problem
bitmap with pairs
Test
CPPTemplate
Grundy Number
C++
QP