ncr, C++ (gcc) - rextester

Language: Layout:

//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));
	}
}

Show compiler warnings [ + ] Compiler args [ + ] Show input