擴(kuò)展歐幾里得算法原理
求解逆元的方法（本文采用擴(kuò)展歐幾里得算法進(jìn)行求解）
求組合數(shù)的兩種方法
Lucas定理

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>


using namespace std;

// 擴(kuò)展歐幾里得算法求方程ax+by=gcd(a,b)的一個(gè)解
// 返回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ù)，對(duì)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;
}