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就是二分的条件!

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; int gcd(int x, int y){
return y== ? x : gcd(y, x%y);
} int lcm(int x, int y){
return x*y/gcd(x, y);
} int main(){
long long ld = , rd = 100000000000000ll, mid;
long long c1, c2, x, y;
cin>>c1>>c2>>x>>y;
while(ld <= rd){
mid = (ld + rd)>>;
long long s1 = mid/x, s2 = mid/y, s3 = mid/lcm(x, y);
if(mid-s1 >= c1 && mid-s2 >= c2 && mid-s3 >= c1+c2) rd = mid-;
else ld = mid+;
}
cout<<rd+<<endl;
return ;
}
上一篇:Docker CE的安装 与镜像加速


下一篇:ASP.NET读取配置文件发送邮件