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 }

View Code

轉載于:https://www.cnblogs.com/hujunzheng/p/4049969.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531598.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531598.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531598.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！