[백준] 6064번: 카잉 달력 - C++

문제 출처:https://www.acmicpc.net/problem/6064

---

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

문제 자체가 약간 난해한 면이 있지만 몇번 읽어보면 규칙을 파악 할 수 있을겁니다.

해를 표현하는 방법은 문제에 나와있는 그대로 <M:N> 이 주어졌을때 년도를 <X:Y>로 표현한다면 X,Y는 1,1로 시작해서 

1씩 증가하며 X>M이 되면 X%M, Y>N이 되면 Y%N을 해주면 됩니다. 

따라서 문제로 M,N,X,Y가 주어졌을때 <X,Y> 가 몇번째 해인지 알기 위해선 위의 조건을 적용시켜 1,1부터 시작하여 증가시키

며 검사하면 됩니다. 그러나 문제는 <X,Y>로 표현할 수 없는 해가 주어진다는 것인데 이 때 무한 반복을 하지 않으려면 처음

부터  반복의 끝을 정해주어야 합니다.

그리고 이 반복의 끝이 바로 문제에 나오는 '종말의 해' 인데 이 날을 구하는 방법은 바로 N과 M의 최소 공배수를 구하는 것입

니다. 이 N과 M의 최소공배수를 G라고 한다면 이 G번째 해가 달력의 마지막이기 때문에 첫번째 해부터 G번째 해까지 <X,Y>

로 표현되는 해가 없다면 <X,Y> 가 유효하지 않은 표현이고 따라서 -1을 출력해주면 되는겁니다.

최소 공배수를 구하는 방법은 유클리드 호제법을 이용하였습니다. 

최대 공약수 공식(gcd)

1. a,b: 최대 공약수를 구하고자 하는 두 수 

2. r: a를 b로 나눈 나머지 r=a%b

3. 식: gcd(a,b)=gcd(b,r) 을 b가 0이 될때까지 반복해주면 됩니다.

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

최소 공배수 공식(lcm)

1. a,b: 최소 공배수를 구하고자 하는 두 수

2. gcd(a,b): a,b의 최대 공약수

3 식: a*b/gcd(a,b)

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

전체 코드입니다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
 
using namespace std;
 
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
 
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
 
int main(void)
{
    int t, m, n, x, y, i, j;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d %d %d %d", &m, &n, &x, &y);
        int limit = lcm(m, n);
        for (j = x; j <= limit; j += m) {
            int temp = (j%n == 0) ? n : j % n;
            if (temp == y) {
                printf("%d\n", j);
                break;
            }
        }
        if (j > limit)
            printf("-1\n");
    }
    return 0;
}