首页 > 代码库 > codeforces B. Friends and Presents(二分+容斥)
codeforces B. Friends and Presents(二分+容斥)
题意：从1....v这些数中找到c1个数不能被x整除，c2个数不能被y整除！
并且这c1个数和这c2个数没有相同的！给定c1, c2, x, y， 求最小的v的值！
思路： 二分+容斥，二分找到v的值，那么s1 = v/x是能被x整除的个数
s2 = v/y是能被y整除数的个数，s3 = v/lcm(x, y)是能被x,y的最小公倍数
整除的个数！
那么 v-s1>=c1 && v-s2>=c2 && v-s3>=c1+c2就是二分的条件！
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 7 int gcd(int x, int y){ 8 return y==0 ? x : gcd(y, x%y); 9 }10 11 int lcm(int x, int y){12 return x*y/gcd(x, y);13 }14 15 int main(){16 long long ld = 1, rd = 100000000000000ll, mid;17 long long c1, c2, x, y;18 cin>>c1>>c2>>x>>y;19 while(ld <= rd){20 mid = (ld + rd)>>1;21 long long s1 = mid/x, s2 = mid/y, s3 = mid/lcm(x, y);22 if(mid-s1 >= c1 && mid-s2 >= c2 && mid-s3 >= c1+c2) rd = mid-1;23 else ld = mid+1;24 } 25 cout<<rd+1<<endl;26 return 0;27 }
codeforces B. Friends and Presents(二分+容斥)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。