当前位置:Gxlcms > mysql > B.FriendsandPresents(CodeforcesRound#275(div2)

B.FriendsandPresents(CodeforcesRound#275(div2)

时间:2021-07-01 10:21:17 帮助过:33人阅读

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;
}

人气教程排行