# 11618 - pB - Birthday Party
>author: Utin
###### tags: `math`

---

## Brief
有n個人圍成一圈（編號1~n），每數k個人發一顆氣球，當發到已有氣球的人時即停止，則此時編號為(n, k)最大公因數的人均會拿到氣球。又發了3次不同顏色之氣球，則最後擁有3色汽球的人數即為：

總人數 / 每次(n, k)最大公因數的最小公倍數

## Solution 0

#include <stdio.h>

#define lcm(a, b) (a / gcd(a, b) * b)

long long gcd(long long n, long long k);

int main() {
    int T;
    long long n, r, b, y, R, B, Y, d;
    scanf("%d", &T);
    while (T--) {

        // input
        scanf("%lld %lld %lld %lld", &n, &r, &b, &y);

        // GCD
        R = gcd(n, r);
        B = gcd(n, b);
        Y = gcd(n, y);

        // LCM
        d = lcm(lcm(R, B), Y);

        // output
        printf("%lld\n", n / d);
    }
}

// Euclidean algorithm
long long gcd(long long n, long long k) {
    while (k) {
        long long tmp = n % k;
        n = k;
        k = tmp;
    }
    return n;
}

// By Utin

## Reference