FZU 2020 组合数求模

我是数论弱渣，于是准备学一点记录一点。。。。

http://acm.fzu.edu.cn/problem.php?pid=2020

http://hi.baidu.com/aekdycoin/item/e051d6616ce60294c5d249d7

这个题是求C(n,m) % k

1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数

我就当成了p是一般的数来练了。。。。

注意到m比较小，于是可以暴力计算。。但是组合数要做除法，没办法，要计算(a/b)%mod，于是要计算b对p的逆元，由于p是随便给的，于是b有可能与p不互质，那样就没有逆元了，，悲剧。。。

不过不用担心，上面的链接中已经有了一个非常nice的解决方法。

我们要乘以分母的逆元，就要使得分母与p互质

那么将分子分母中p的质因子都去掉,形成一个新的分数

a1*a2*a3..../b1*b2*b2

现在分母中的每个数都与p互质，那现在就可以乘以分母的逆元算过去了，但是别忘了分子分母中被抠掉的那些质因子，还是要乘回去的哦

分子的每种质因子的个数肯定是大于分母的，所以是乘回那些抠掉的质因子。

#include<cstdio>#include<iostream>using namespace std;typedef long long lld;const int maxn = 100010;bool vis[maxn];int pr[maxn];int cntp;void init(){for(int i = 2; i <= 100000; i++){for(int j = 2*i;j <= 100000; j+=i){vis[j] = true;}}for(int i = 2; i <= 100000; i++) if(!vis[i]){pr[cntp++] = i;}}int tot;int Cnt[20],np[20];int n , m , mod;void split(int num){tot = 0;memset(Cnt,0,sizeof(Cnt));for(int i = 0; i < cntp; i++){if(num%pr[i]==0) np[tot++] = pr[i];for(;num%pr[i]==0;num/=pr[i]) Cnt[tot-1]++;}if(num > 1) np[tot]=num,Cnt[tot++]  = 1;}int exgcd(int a,int b,int &x,int &y){    if(b==0) {x=1;y=0;return a;}    else     {        int d=exgcd(b,a%b,x,y);        int t=x;        x=y;        y=t-a/b*y;        return d;    }}int inverse(int num,int mod){    int x,y;exgcd(num,mod,x,y);while(x<0) x+=mod,y-=num;return x;}lld Pow(lld a,int b,int mod){lld ans = 1;while(b){if(b&1) ans = ans * a % mod;a = a * a % mod; b>>=1;}return ans ;}int now[20];int h[20];void gao()//求C(n,m)%mod,先将C(n,m)中那些与mod有关的因子去掉，这样做除法的时候就可以取逆了{memset(now,0,sizeof(now));memset(h,0,sizeof(h));long long ans = 1;for(int i = 1; i <= m; i++){int fenzi = n - i + 1;int fenmu = m - i + 1;for(int j = 0 ;j < tot; j++){for(;fenzi%np[j]==0;) fenzi /= np[j],h[j]++;for(;fenmu%np[j]==0;) fenmu /= np[j],h[j]--;}ans = ans * fenzi % mod;ans = ans * inverse(fenmu,mod) % mod;}for(int j = 0; j < tot; j++){ans = ans * Pow(np[j],h[j],mod) % mod;}printf("%lld\n",ans);}void brute(){freopen("ii.txt","w",stdout);long long c[50][50];c[0][0] = 1;int mod = 1145;for(int i = 1; i < 50; i++){c[i][0] = c[i][i] = 1;for(int j = 1;j < i; j++){c[i][j] = c[i-1][j] + c[i-1][j-1];}}int t = 0;printf("210\n");for(int i = 1; i <= 20; i++){for(int j = 0;j < i; j++){t++;printf("%d %d %d\n",i,j,mod);}}}int main(){//brute();#ifndef ONLINE_JUDGEfreopen("ii.txt","r",stdin);freopen("out.txt","w",stdout);#endif init();int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&mod);split(mod);gao();}return 0;}