6064번: Cain Calendar

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

d = GCD(m,n)
확장 유클리드 알고리즘을 이용해 mu - nv = y-x (n/d > u >= 0, m/d > v >= 0)인 u, v를 찾는다.

시간복잡도는 테스트 케이스마다 $O(\lg(min(m,n)))$

#include<cstdio>
#include<algorithm>
int n, m, x, y, t;
int ee(int a, int b, int &u, int &v) {
    if (!b) {
        u = 1;
        v = 0;
        return a;
    }
    int ret = ee(b, a%b, v, u);
    v -= a / b*u;
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d%d", &m, &n, &x, &y);
        int u, v, ret = ee(m, -n, u, v);
        if ((y - x) % ret) { puts("-1"); continue; }
        int p = abs(n / ret);
        printf("%d\n", (u*(y - x) / ret%p + p) % p*m + x);
    }
    return 0;
}