HDU 5768 Lucky7

2019-04-13 14:33发布

站内文章 / 模拟电子
17908 0 1254
class="markdown_views prism-atom-one-light"> 题目链接：
http://acm.split.hdu.edu.cn/showproblem.php?pid=5768 题目大意：求出一个区间内模7余0，但是模一些给定的互素的数不等于其给定的值的数的个数。如求1-100中模7余0，但是不能模3余2，模5余3的数的个数。 解题思路：首先可以知道通过中国剩余定理能求出一个区间内模3余2，模5余3，等式的所有解，这道题就是在模7余0的基础上求那些式子的并集，用容斥定理就好了。 中国剩余定理： 这里写图片描述 容斥定理：《挑战程序设计竞赛》295页 AC代码： #include #include #include #include #include #include #define RI(N) scanf("%d",&(N)) #define RII(N,M) scanf("%d %d",&(N),&(M)) #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K)) #define mem(a) memset((a),0,sizeof(a)) using namespace std; const int inf=1e9+7; const int inf1=-1*1e9; double EPS=1e-10; typedef long long LL; int a[100]; int m[100]; int cond1[100]; int cond2[100]; LL extent_Euclid(LL a,LL b,LL &x,LL &y); LL x2,y2; LL quik_cheng(LL a,LL b,LL m) { LL res=0; while(a) { if(a&1) res=(res+b)%m; b=(b*2)%m; a>>=1; } return res; } LL CRT(int a[],int m[],int n) { LL M=1; LL ans=0; for(int i=0;ifor(int i=0;iwhile(ans<0) ans+=M; ans=ans-ans/M*M; if(ans>y2) return 0; if(ans>=x2&&ans<=y2) { LL tt=(y2-ans)/M+1; return tt; } if(ans1; LL y3=y2-ans; LL tt=y3/M-x3/M; return tt; } } int main() { int T,n,casee=1; RI(T); while(T--) { RI(n); scanf("%I64d%I64d",&x2,&y2); a[0]=0;//a为取余等于几 m[0]=7;//m为取余的数 for(int i=0;i0; /*for(int i=0;i for(int i=1;i<(1<int num=0; int poi=1; for(int j=i;j!=0;j>>=1) num+=j&1; for(int j=0;jif((i>>j)&1) { a[poi]=cond2[j]; m[poi]=cond1[j]; poi++; } } if(num%2==1) ans+=CRT(a,m,poi); else ans-=CRT(a,m,poi); } printf("Case #%d: %I64d ",casee,y2/7-(x2-1)/7-ans); casee++; } return 0; } LL extent_Euclid(LL a,LL b,LL &x,LL &y) { LL d=a; if(b!=0){ d=extent_Euclid(b,a%b,y,x); y-=(a/b)*x; } else{ x=1; y=0; } return d; }

热门文章