首页 > 代码库 > HDU 5768 Lucky7（CRT+容斥原理）
HDU 5768 Lucky7（CRT+容斥原理）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5768
【题目大意】
求出一个区间内7的倍数中，对于每个ai取模不等于bi的数的个数。
【题解】
首先，对于x mod 7=0，和选取的一些x mod ai=bi，我们可以利用CRT解出最小的x值，那么这样子我们就可以对所有的aibi选取方式做容斥，得到x mod 7=0成立且所有x mod ai=bi不成立的x的个数。也就是答案。
【代码】
#include <cstdio>#include <algorithm>#include <cmath>using namespace std;typedef long long LL;LL a[20],b[20],l,r;int T,n,Cas=1,vis[20];LL pow(LL a,LL b,LL p){LL t=1;for(a%=p;b;b>>=1LL,a=a*a%p)if(b&1LL)t=t*a%p;return t;}LL Cal(LL r,LL l,LL m){return (r-l)/m;}LL CRT(LL*a,LL*b,int n){ LL ans=0,P=1; for(int i=0;i<n;i++)if(vis[i])P*=a[i]; for(int i=0;i<n;i++)if(vis[i])ans=(ans+(P/a[i])*pow(P/a[i],a[i]-2,a[i])%P*b[i]%P)%P; while(ans<0)ans+=P; return Cal(r+P,ans,P)-Cal(l-1+P,ans,P);}int main(){ scanf("%d",&T); a[0]=7;b[0]=0;vis[0]=1; while(T--){ scanf("%d%lld%lld",&n,&l,&r); for(int i=1;i<=n;i++)scanf("%d%d",a+i,b+i),vis[i]=0; LL ans=0; int all=1<<n; for(int i=0;i<all;i++){ int U=i,cnt=0; for(int j=1;j<=n;j++)vis[j]=U&1,U>>=1,cnt+=vis[j]; cnt=cnt&1?-1:1; ans+=1LL*cnt*CRT(a,b,n+1); }printf("Case #%d: %lld\n",Cas++,ans); }return 0;}
HDU 5768 Lucky7（CRT+容斥原理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。