백준 6064 (카잉 달력) c++

문제

6064번: 카잉 달력

m과 n이 주어지고 x와 y가 주어지면 <x, y>가 몇번째로 이루어지는지 구하는 문제입니다.

만약 <x, y>가 안되면 -1을 출력하면 됩니다.

<1, 1> 부터 시작하며 x' n을 넘어가면 다시 x'가 1로 되고 y도 마찬가지 입니다.

예를 들어 m과 n이 10, 12 라면

<1, 1> 부터 시작해 <10, 10> 까지 가고 <11, 11>은 x'가 m을 넘어가 되므로 <10, 10> 다음에는 <1, 11> 이 됩니다.

마찬가지로 <2, 12>가 되고 다음 순서는 <3, 13> 이 되어야 하지만 y'가 n을 넘어가게 되므로 <3, 12>가 됩니다.

 

<10, 12> 는 60번째 에서 마지막이 되고 끝이 납니다.

 

단순히 <x, y>가 될 때 까지 반복문을 돌리게 되면 시간초과가 나게 됩니다.

 

따라서 새로운 방법을 구해야 합니다.

요점은 바로 x를 기준으로 맞춘다는 것입니다. 즉, x를 기준으로 하면 y만 신경 써주면 됩니다.

예를 들어 m과 n이 <10 ,12> 이고 x와 y가 <3, 9> 라면

x가 3이므로 3일 경우에만 y를 판별해 주면 됩니다.

y는 n까지 증가하므로 나머지 연산을 통해 판별해주면 됩니다. 

먼저 처음에 x = 3일 경우

x = 3

y = 3 % 12 = 3

 

다음에 x가 3일 경우에는 x는 m만큼 증가 하므로 m을 더해주면 됩니다.

x = (3 + 10) = 3

y = (3 + 10) % 12 = 1

 

x = ( 3 + 10 + 10) = 3

y = (3 + 10 + 10) % 12 = 11

 

x = (3 + 10 + 10 + 10) = 3

y = (3 + 10 + 10 + 10) % 12 = 9

따라서 (3 +10 +10 +10)번의 연산을 했을 때 <3, ,9> 가 나오므로 정답은 (3 + 10 + 10 +10) = 33이 됩니다.

 

하지만 만약 답이 될 수 없는 경우도 있습니다. 그렇게 되면 계속 해서 반복문이 실행이 되고 결국 시간초과가

나오게 됩니다.

문제에서의 힌트는 m과 n이 <10, 12>의 경우에는 최종 해가 <10, 12> 가 되어 60번째에서 끝이 나게 됩니다.

즉, m과 n의 최소공배수에서 끝이 납니다. 

만약 최소공배수를 넘어가게 되면 해당 x와 y는 답이 될 수 없습니다.

다음과 같이 gcd를 먼저 구해주면 lcm(최소공배수)를 구할 수 있습니다.

lcm으로 나온 수를 lim에 넣어주고 lim까지 반복문을 돌려 줍니다.

i가 lim을 넘어가게 되면 정답이 없는 것이므로 -1을 출력해줍니다.

---

전체 코드 입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int gcd(int a, int b);
int lcm(int a, int b);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int m, n, x, y, i;
        cin >> m >> n >> x >> y;
        int lim = lcm(m, n);
        for (i = x; i <= lim; i += m) {
            int temp = (i % n == 0) ? n : i % n;
 
            if (temp == y) {
                cout << i << '\n';
                break;
            }
        }
        if (i > lim)
            cout << -1 << '\n';
    }
 
 
 
    return 0;
}
int gcd(int a, int b) {
    if (!b)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}