ZCMU—1780

1780: LoL？

Time Limit: 1 Sec  

Memory Limit: 128 MB

[​​Submit​​][​​Status​​][​​Web Board​​]

Description

校園的生活是美好的，學習之餘，大家都有着自己的休閑方式，聽音樂，看電影，打遊戲什麼的，說到遊戲，不得不說一個很有意思的遊戲，這個遊戲中需要兩位同志配合一起，開始的時候隻能靠攻擊小兵掙錢，掙錢的規則是誰最後打死這個小兵那麼誰就可以獲得25塊錢....,某日，一對基佬A,a玩起了這個遊戲，現在知道A的攻擊速度是每一秒可以攻擊小兵n下，a的攻擊速度是每一秒可以攻擊小兵m下，現在二人都做好了攻擊準備，那麼最後小兵會是誰打死的？

Input

第一行T(T<=100000),第二行n,m,x(n,m<=10^6)。n表示A的攻速，m表示a的攻速，x（x<=10^9）表示小兵血量（a，A每攻擊小兵一次，小兵扣除1滴血

Output

Case #x: y,x是測試編号從1開始，y表示答案，如果A最後打死小兵，y為'A'，若果同時打死，y為'Both',否則y為'a'

Sample Input

4

3 2 1

3 2 2

3 2 3

3 2 4

Sample Output

Case #1: A

Case #2: a

Case #3: A

Case #4: Both

HINT

樣例1，小兵血量是1，A在1/3秒攻擊小兵，是以A擊殺小兵，樣例4，1/3秒A攻擊小兵，1/2秒a攻擊，2/3秒A攻擊，2/2,3/3是二者同時攻擊

【分析】

從一開始就有感覺是要用到公倍數或者公約數，并且顯然有一個優化就是x%(n+m)  也就是多餘的整秒的掉血全部去掉，這樣就隻需要考慮在被打死的那一秒内的情況了。

但是對小數的公約數非常麻煩，那麼為什麼不考慮把1/3和1/2擴大呢？對2,3這組資料，一秒擴大成6個機關時間，那麼攻速為2的人在這六份裡攻擊了三次，攻速為3的攻擊了兩次，是以很顯然擴大之後兩個人的攻速是lcm/m和lcm/n  （當然要記得并不是互換，考慮一下4 6這個情況就知道了。）

這樣可以看到，對第i個位置，被打掉的血量就是i/x1+i/x2

這時候就可以考慮二分答案了，如果被打掉的血量比他的剩餘血量多，那麼說明答案在左邊，否則答案在右邊，打掉的血量剛好等于剩餘血量那麼就已經有答案了。

當然要考慮一個特殊情況  也就是說找到的這個時間點剛好兩個人同時攻擊并且打掉的血量比剩餘血量多1，也就是在這一秒被打死了，但是打掉的血量=剩餘血量+1  這種情況導緻我wa了一次...果然還是自己的思路不夠清晰

【代碼】

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
  int T;
  scanf("%d",&T);
  long long n,m,x,d,e,f,xx,right,left,mid;
  for(int t =1; t<=T;t++){
    scanf("%lld%lld%lld",&n,&m,&x);
    x %= (n+m);
    printf("Case #%d: ",t);
    if (x==0) printf("Both\n");
    else
    {
      d=n,e=m;
          while(e!=0)
          {
            f=d%e;
            d=e;
            e=f;
        }
        right=n*m/d;
        d=n;e=m;
        n=right/d;
        m=right/e;
      left=0;
      while (left<=right)
      {
        mid=(left+right)/2;
        xx=mid/n+mid/m;
        if (xx-x==1 && mid%n==0 && mid%m==0) 
        {
          printf("Both\n");goto out;
        }
        if (x==xx)
        {
          if (mid%n==0 && mid%m==0)
          {
            printf("Both\n");goto out;
          }
          if (mid%n==0) 
          {
            printf("A\n");goto out;
          }
          if (mid%m==0)
          {
            printf("a\n");goto out;
          }
          right=mid;
        }
        else
        {
          if (xx>x) right=mid-1;
          else left=mid+1;
        }
      }
      
      out:;
    }
  }
}