擴展歐幾里得算法原理
求解逆元的方法（本文采用擴展歐幾里得算法進行求解）
求組合數(shù)的兩種方法
Lucas定理
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
// 擴展歐幾里得算法求方程ax+by=gcd(a,b)的一個解
// 返回a粗悯，b的最大公約數(shù)
int exGcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1;
y = 0;
return a;
}
int g = exGcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return g;
}
//求解a模m的逆元的最小整數(shù)解
int inverse(int a, int m){
int x, y;
int g = exGcd(a, m, x, y);
return (x % m + m) % m;
}
//n中選m的組合數(shù)怎栽，對p取余的結(jié)果
int Cal(int n, int m, int p){
int res = 1;
for(int i = 1; i <= m; i++){
res = res * (n - m + i) % p;
res = res * inverse(i, p) % p;
}
return res;
}
//Lucas定理求解組合數(shù)
int Lucas(int n, int m, int p){
if(m == 0)
return 1;
int C = Cal(n % p, m % p, p);
return C * Lucas(n / p, m / p, p) % p;
}
int main(){
int n, m, p;
while(scanf("%d%d%d", &n, &m, &p) != EOF){
printf("%d\n", Lucas(n, m, p));
}
return 0;
}
