Game of Peace

Time Limit: 1000ms, Special Time Limit:2500ms,Memory Limit:32768KB

Total submit users: 47, Accepted users:27

Problem 13778 : No special judgement

Problem description

Bob has learned a new magic trick that needs a very special preparation. Once he masters the trick he will be able to bring peace to the world, but if he fails, the world will be destroyed. The preparation is performed as follows: There are two containers, initially one is empty and the other one has X marbles. Bob has a Marble Cloning Machine, it clones the marbles in the container with the larger number of marbles, then pours the new clones into the other container (e.g. if the two containers have 7 and 4 marbles, after the cloning step they will have 7 and 11 marbles). The machine does this cloning operation exactly M times. However, there is a bug in the machine, after it performs N cloning operations (N ≤ M), it will add Y extra marbles to the container with the larger number of marbles. Then the machine will continue normally with the cloning operation exactly M − N times. During the cloning operations, if both containers have the same number of marbles, any of them can be considered the one with the larger number of marbles. Now, the bug in Bob’s machine is threatening to destroy the world. But his nerdy friend Alice told him that she knows how to fix it. All he has to do is to calculate the greatest common divisor of the sizes of the two containers after the cloning machine is done. Can you help Bob save the world?

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 1,000) representing the number of test cases. Followed by T test cases. Each test case will consist of a single line, containing 4 integers separated by a single space X, N, Y and M (1 ≤ X, Y ≤ 1,000) (0 ≤ N ≤ 70) (N ≤ M ≤ 100,000) which are the numbers as described above.

Output

For each test case print a single line containing “Case n:” (without quotes) where n is the test case number (starting from 1) followed by a space then the greatest common divisor of the sizes of the two containers after the machine is done.

Sample Input

2 4 3 6 5 5 1 15 2

Sample Output

Case 1: 2 Case 2: 5

Judge Tips

In the first sample test case, the number of marbles in each container will be the following after each step: (4, 0), (4, 4), (4, 8), (12, 8), (18, 8), (18, 26), (44, 26). The greatest common divisor of 44 and 26 is 2.

Problem Source

ACM International Collegiate Programming Contest, Arab Collegiate Programming Contest 2014 Egypt, Sharm El Sheikh, November 16th, 2014 其實這一道題一看覺得其實就是一道挺簡單的題目。。。。。。但是超級多坑啊-。- 1、就是。。。。。。你要注意它可以操作十萬次。。。。。。 你一個瓶子裡面的小球球很快就可以超出資料類型了。。。。。。是以說，這裡暗示了我們是不能強算的。 這裡有一個小要點（最後說hh） 2、要注意。。。。。。有沒有想過操作0次的情況呢？也就是說我們隻會出現一次bug後進行輸出。 3、0和别的數字的最大公因數怎麼算呢？是這個數本身 4、想到了一開始我提到了不能強算的那個留下的一個要點嗎~嘻嘻(●'◡'●)其實就是說，當你出現了第一次bug之後就可以不用算了，因為後續的操作對兩個瓶子裡面的球球的最大公因數并沒有影響~我們假設瓶子1裡面有x個球球 x=a*b*c*d先這樣子做一下假設，不一定有四項其中能知道的就是，x可以拆分成素數相乘瓶子2裡面有y個球球，y=e*f*g*a，其中也是做一下假設而已~不一定有四項，其中能知道的就是，y可以拆分成素數相乘 我們按照題目這樣子clone，每次能做的，就是。 a*b*c*d+e*f*g*a=e*f*g*a a(b*c*d+e*f*g)=e*f*g*a (假設y比x大），我們可以看到，這樣子加來加去是不會改變最大公因數的。 唯一可能出現變化的，就是出的那次bug額外加的球球。 是以說，這個就是最關鍵的地方。 代碼稍後在評論貼出~~~ -------評論有字數限制~~ 還是在文章裡面修改好了 #include<iostream> #include<stdio.h> using namespace std; long long gcd(long long a, long long b) {     for (long long r = a%b; r != 0; r = a%b)     {         a = b;         b = r;     }     return b; } int main() {     int n = 0;     while (cin >> n)     {         for (int i = 1; i <= n; i++)         {             long long container1 = 0;             long long container2 = 0;             long long after = 0;             long long add = 0;             long long all = 0;                  scanf("%I64d%I64d%I64d%I64d", &container2, &after, &add, &all);             //cout<<container2<<after<<add<<all;             if (all == 0)             {                 cout << "Case " << i << ":" << " " << container2+add<< endl;                 continue;             }             if (after == 0)             {                 cout << "Case " << i << ":" << " " << container2+add<< endl;                 continue;             }             for (int k = 0, now = 0; k < all; k++)             {                 if (container2 > container1)                 {                 container1 = container1 + container2;                     now++;                 if (now == after)                     {                         container1 = container1 + add;                         break;                     }                 }                 else                 {                     container2 = container2 + container1;                     now++;                     if (now == after)                     {                         container2 = container2 + add;                             break;                     }                 }             }             long long tmp = 0;             if (container2 > container1)             {                 tmp = container1;                 container1 = container2;                 container2 = tmp;             }             //    cout<<container1<<" "<<container2<<endl;             cout << "Case " << i << ":" << " " << gcd(container1, container2) << endl;         }     } }