Problem Description
给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！ 给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！
Input
输入数据第一行是一个正整数T,表示数据组数 (T <= 100) 接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数) 输入数据第一行是一个正整数T,表示数据组数 (T <= 100) 接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)
Output
对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。 对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。
Sample Input
25 2 35 2 61 25 2 35 2 61
Sample Output
110 110
//当取模的p小于1e9时,不用预处理 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef long long ll; //计算n的k次方对M取模，二分法 ll Pow(ll n, ll k, ll p){ ll ans=1; while(k){ if(k&1) ans=(ans*n)%p; n = (n*n)%p; k>>=1; //k=k>>1 k=k/2； } return ans; } ll C(ll n,ll m,ll p){ if(m==0) return 1; if(m>n-m) m=n-m; ll up=1,down=1; for(int i=1;i<=m;i++){ up = (up*(n-i+1))%p; down=(down*i)%p; } return up*Pow(down,p-2,p)%p; } ll lucas(ll n,ll m,ll p){ if(m==0) return 1; return C(n%p,m%p,p)*lucas(n/p,m/p,p); } int main(){ int t=1; ll m,n,p; scanf("%d",&t); while(t--){ scanf("%I64d%I64d%I64d",&n,&m,&p); printf("%I64d
",lucas(n,m,p)); } return 0; }
Problem Description 给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！ Input 输入数据第一行是一个正整数T,表示数据组数 (T <= 100) 接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数) Output 对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。 Sample Input 25 2 35 2 61 Sample Output 110 //当取模的p小于1e9时,不用预处理 #include
#include
#include
using namespace std; typedef long long ll; //计算n的k次方对M取模，二分法 ll Pow(ll n, ll k, ll p){ ll ans=1; while(k){ if(k&1) ans=(ans*n)%p; n = (n*n)%p; k>>=1; //k=k>>1 k=k/2； } return ans; } ll C(ll n,ll m,ll p){ if(m==0) return 1; if(m>n-m) m=n-m; ll up=1,down=1; for(int i=1;i<=m;i++){ up = (up*(n-i+1))%p; down=(down*i)%p; } return up*Pow(down,p-2,p)%p; } ll lucas(ll n,ll m,ll p){ if(m==0) return 1; return C(n%p,m%p,p)*lucas(n/p,m/p,p); } int main(){ int t=1; ll m,n,p; scanf("%d",&t); while(t--){ scanf("%I64d%I64d%I64d",&n,&m,&p); printf("%I64d
",lucas(n,m,p)); } return 0; }
