[백준] 6064번 카잉 달력

문제: 6064번: 카잉 달력

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

// c++11 이하는 GCD, LCM 메서드 직접 만들어야 함;;
// 최대공약수 (GCD) - 유클리드 알고리즘
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 최소공배수 (LCM) - GCD 를 이용한 공식
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t-- > 0) {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
        bool flag = false;

        int target = lcm(m, n);
        for (int i = x; i <= target; i += m) {
            if ((i - 1) % n + 1 == y) {
                cout << i << "\n";
                flag = true;
                break;
            }
        }
        if (!flag)
            cout << -1 << "\n";
    }

    return 0;
}