11799번: Game of Peace

https://www.acmicpc.net/problem/11799


$O(t*(n+\lg (x+y))$

처음 n번은 큰 수에 작은 수를 더한다.
유클리드 호제법에 의해 답은 gcd(큰 수+y,작은 수)가 된다.

#include<stdio.h>
typedef long long ll;
int t, n, m, x, y;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int main() {
    scanf("%d", &t);
    for (int j = 1; j <= t; j++) {
        scanf("%d %d %d %d", &x, &n, &y, &m);
        ll a = x, b = 0;
        for (int i = 0; i < n; i++) {
            b += a;
            if (a < b) a ^= b ^= a ^= b;
        }
        printf("Case %d: %lld\n", j, gcd(a + y, b));
    }
    return 0;
}