B.FriendsandPresents（CodeforcesRound#275(div2)

Note In the first sample you give the set of numbers {1,?3,?5} to the first friend and the set of numbers {2} to the second friend. Note that if you give set {1,?3,?5} to the first friend, then we cannot give any of the numbers 1 , 3 , 5 t

Note

In the first sample you give the set of numbers {1,?3,?5} to the first friend and the set of numbers {2} to the second friend. Note that if you give set {1,?3,?5} to the first friend, then we cannot give any of the numbers 1 , 3 , 5 to the second friend.

In the second sample you give the set of numbers {3} to the first friend, and the set of numbers {1,?2,?4} to the second friend. Thus, the answer to the problem is 4 .

二分渣渣把二分又写跪了，总是分不清l与r的关系o(╯□╰)o，我竟然l和r都判断了一下。这题竟然l和r都能过。

这题就是枚举一下中间结果，对a周期为x-1，b周期为y-1，只有当i为y的倍数时，只能让a取，当i为x的倍数时，只

能让b取，算一下x，y的倍数时两个都不能取得，a的总数量减去只能a取的，b的总数量减去只能b取的 ，剩下的要

取的和小于等于两个都能取得，这个值就是有效值。

代码：

#include  
#include  
#include 
using namespace std;
long long cnt1,cnt2,x,y;
long long gcd(long long a,long long b)
{
    return b==0?a:gcd(b,a%b);
}
bool judge(long long v)
{
    long long t1,t2,t3;
    t1=v/x;
    t2=v/y;
    t3=v/(x*y/gcd(x,y));
    long long temp1,temp2,temp3;
    temp1=max((long long)0,cnt1-t2+t3);//t2-t3是只能a取的，cnt1-只能a取的，就是剩下a没取的
    temp2=max((long long)0,cnt2-t1+t3);//t1-t3是只能b取的，cnt2-只能b取的，就是剩下b没取的
    temp3=max((long long)0,v-t1-t2+t3);//x，y都能取的
    if(temp3>=temp1+temp2)//a，b都能取的大于要大于等于a，b没取的和
    return true;
    else
    return false;
}
int main()
{
    scanf("%I64d%I64d%I64d%I64d",&cnt1,&cnt2,&x,&y);
    long long l=1,r=2000000000;
    long long u=0;
    while(l >1;
        if(judge(m))
        {
            u=m;
            r=m;
        }
        else
        {
            l=m+1;
        }
    }
   // long long ans;
   // if(judge(r))
   // ans=r;
 //   else
  //  ans=l;
    printf("%I64d\n",u);
    return 0;
} 

查看更多关于B.FriendsandPresents（CodeforcesRound#275(div2)的详细内容...