首页 > 代码库 > HDU 5446 Unknown Treasure（Lucas定理+CRT）
HDU 5446 Unknown Treasure（Lucas定理+CRT）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5446
【题目大意】
给出一个合数M的每一个质因子，同时给出n,m，求C(n,m)%M。
【题解】
首先我们可以用Lucas定理求出对答案对每个质因子的模，然后我们发现只要求解这个同余方程组就可以得到答案，所以我们用中国剩余定理解决剩下的问题。
【代码】
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int N=100005;LL f[N],rf[N];LL mul(LL x,LL y,LL P){return (x*y-(LL)(x/(long double)P*y+1e-3)*P+P)%P;}LL pow(LL a,LL b,LL P){LL t=1;for(;b;b>>=1,a=mul(a,a,P))if(b&1)t=mul(t,a,P);return t;}void init(int n){ f[0]=1;for(int i=1;i<n;i++)f[i]=f[i-1]*i%n; rf[n-1]=pow(f[n-1],n-2,n); for(int i=n-1;i;i--)rf[i-1]=rf[i]*i%n;}LL C(int n,int m,int mod){ if(m>n||m<0||n<0)return 0; return f[n]*rf[m]%mod*rf[n-m]%mod;}LL lucas(LL n,LL m,LL P){ if(n<m)return 0; if(!m||n==m)return 1; return C(n%P,m%P,P)*lucas(n/P,m/P,P)%P;}LL exgcd(LL a,LL b,LL& x,LL& y){ if(b==0){x=1;y=0;return a;} LL d=exgcd(b,a%b,y,x); y-=x*(a/b); return d;}LL CRT(LL* a,LL* b,int n){ LL P=1,d,y,x=0; for(int i=0;i<n;i++)P*=a[i]; for(int i=0;i<n;i++){ LL w=P/a[i]; exgcd(a[i],w,d,y); y=(y%P+P)%P; x=(x+mul(mul(y,w,P),b[i],P)); }return (x+P)%P;}int T,k;LL n,m,a[15],p[15];int main(){ scanf("%d",&T); while(T--){ scanf("%lld%lld%d",&n,&m,&k); for(int i=0;i<k;i++){ scanf("%lld",&p[i]); init(p[i]); a[i]=lucas(n,m,p[i]); }printf("%lld\n",CRT(p,a,k)); }return 0;}
HDU 5446 Unknown Treasure（Lucas定理+CRT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。