[백준 6064]카잉 달력

[백준 6064]카잉 달력

문제 링크

#include "header.h"
using namespace std;
int T;

int gcd(int a, int b){
    if(a % b == 0) return b;

    return gcd(b, a % b);
}

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

int main(){

    cin >> T;

    for(int i=0; i<T; i++){
        int M, N, x, y;
        cin >> M >> N >> x >> y;

        int limit = lcm(M, N);
        int j = x;
        for(j=x; j<=limit; j+=M){
            int y_temp = j % N;
            if(y_temp == 0) y_temp = N;
            if(y_temp == y){
                cout << j << endl;
                break;
            }
        }
        if(j >= limit){
            cout << -1 << endl;
        }

    }

    return 0;
}

• N과 M의 최소공배수가 지구 멸망의 달이다.
• 최소 공배수를 구하려면 최대 공약수를 알아야 한다. (유클리드 호제법)
• x가 M이 될 때 마다 +1이 되기 때문에, x를 기준으로 한다.
• 기준이 되는 x에서 % N을 한 것이 y가 된다.
• y가 입력으로 주어진 y가 되면 break를 해 준다.
• 이 때, y가 0이 되면, N으로 초기화를 시켜주어야 한다.
• limit를 초과하게 되면, -1을 출력시켜준다.