洛阳网站改版维护公司,网站设计功能,湘潭网站建设 都来磐石网络,深圳市福田建设股份有限公司网站将大组合数C#xff08;n,m#xff09;%p分解为小组合数C#xff08;n,m#xff09;%p乘积的模#xff0c;n10^18,m10^18。
其中求解小组合数可以根据定义式计算#xff08;质因子分解#xff09;#xff0c;也可以通过定义式的变形计算#xff08;逆元…将大组合数Cn,m%p分解为小组合数Cn,m%p乘积的模n10^18,m10^18。
其中求解小组合数可以根据定义式计算质因子分解也可以通过定义式的变形计算逆元
一、定义式计算质因子分解-快速幂
快速幂计算每一组pi^ci%p然后相乘取模
#includestdio.h
//素数表(筛法)
const int maxn1000000;
int prime[maxn];
int pNum0;
bool p[maxn]{false};
void Find_Prime(){for(int i2;imaxn;i){if(p[i]false){prime[pNum]i;for(int jii;jmaxn;ji){p[j]true;}}}
}//n!中含质因子p个数
int cal(int n,int p){int ans0;while(n){ansn/p;n/p;}return ans;
}//快速幂求a^b%p
typedef long long LL;
LL binaryPow(LL a,LL b,LL m){if(b0) return 1;if(b1) return a*binaryPow(a,b-1,m)%m;else{LL mulbinaryPow(a,b/2,m);return mul*mul%m;}
}//小组合数C(n,m)%p
//遍历素数表中每一个质因子计算每一组pi^ci%p然后相乘取模
int C(int n,int m,int p){int ans1;for(int i0;prime[i]n;i){int ccal(n,prime[i])-cal(m,prime[i])-cal(n-m,prime[i]); //C(n,m)中含质因子个数 ansans*binaryPow(prime[i],c,p)%p;}return ans;
} //Lucas定理求大组合数C(n,m)%p
int Lucas(int n,int m,int p){if(m0) return 1;return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
} int main(){Find_Prime();int n,m,p;scanf(%d%d%d,n,m,p);printf(%d,Lucas(n,m,p));return 0;
}
二、定义式的变形计算逆元
#includestdio.h
//扩展欧几里得解出x
int exGcd(int a,int m,int x,int y){if(m0){x1;y0;return a;}int gexGcd(m,a%m,x,y);int tempx;xy;ytemp-(a/m)*y;return g;
}//逆元得0-m范围内的解
int inverse(int a,int m){int x,y;int gexGcd(a,m,x,y);return (x%mm)%m;
}//求小组合数C(n,m)%p
int C(int n,int m,int p){int ans1;for(int i1;im;i){ansans*(n-mi)%p;ansans*inverse(i,p)%p;}return ans;
}//Lucas求大组合数 C(n,m)%pint Lucas(int n,int m,int p){if(m0) return 1;return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;}int main(){int n,m,p;scanf(%d%d%d,n,m,p);printf(%d,Lucas(n,m,p));return 0;}
运行结果
C84,58%52
