[PHP知识库]Lucas定理求大组合数取模

Lucas定理求大组合数取模
HDU3037
http://acm.hdu.edu.cn/showproblem.php?pid=3037

#include<iostream>
#include<stdio.h>
#define LL long long
using namespace std;
LL a,b;
int p;
LL quick_mod(LL a, LL b) {
	LL ans = 1;
	a %= p;
	while(b) {
		if(b & 1) {
			ans = ans * a % p;
			b--;
		}
		b >>= 1;
		a = a * a % p;
	}
	return ans;
}
LL C(LL n, LL m) {
	if(n<m)
		return 0;
	long long a=1,b=1;
	while(m) {
		a=(a*n)%p;
		b=(b*m)%p;
		m--;
		n--;
	}
	return (a*quick_mod(b,p-2))%p;
}
LL Lucas(LL n, LL m) {
	if(m == 0) return 1;
	return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}
int main() {
	int t;
	cin>>t;
	while(t--) {
		cin>>a>>b>>p;
		cout<<Lucas(a+b,b)<<endl;
		//C  n(下标)  m(上标) 
	}
}