[백준/BOJ] 6064번 카잉 달력 (C++)

www.acmicpc.net/problem/6064

6064번: 카잉 달력

M = 5, N = 7, x = 3, y = 4 일 때 다음과 같이 카잉 달력을 나타낼 수 있습니다.

 

1 : <1, 1> 11 : <1, 4>

2 : <2, 2> 12 : <2, 5>

3 : <3, 3> 13 : <3, 6>

4 : <4, 4> 14 : <4, 7>

5 : <5, 5> 15 : <5, 1>

6:  <1, 6> 16 : <1, 2>

7:  <2, 7> 17 : <2, 3>

8 : <3, 1> 18 : <3, 4>

9 : <4, 2> 19 : <4, 5>

10 : <5, 3> 20 : <5, 6>

 

뭔가 위의 경우에서는 뭔가 규칙을 찾아내기 어렵습니다. 위에서 나타낸 카잉 달력의 값들을 전부 1씩 빼보면 어떨까요?

 

0 : <0, 0> 10 : <0, 3>

1 : <1, 1> 11 : <1, 4>

2 : <2, 2> 12 : <2, 5>

3 : <3, 3> 13 : <3, 6>

4 : <4, 4> 14 : <4, 0>

5:  <0, 5> 15 : <0, 1>

6:  <1, 6> 16 : <1, 2>

7 : <2, 0> 17 : <2, 3>

8 : <3, 1> 18 : <3, 4>

9 : <4, 2> 19 : <4, 5>

 

x쪽은 M의 나머지의 값을, y쪽은 N의 나머지의 값을 차례대로 가지는 것을 확인할 수 있습니다. 뿐만 아니라 x = 3인 경우만 생각해봤을 때 3, 8, 13, 18 공차가 5인 등차수열을 가집니다. 그리고 이 등차수열의 값을 N으로 나눈 나머지가 y의 값과 같은 것을 알 수 있습니다. 즉 x = 3, y = 4인 값을 찾기 위해서 처음부터 끝까지 탐색하는 것이 아니라, x = 3인 경우만 쭉 찾아가면서 시간복잡도를 줄일 수 있습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin>>t;
    while(t--) {
    	bool flag = false;
    	int m, n, x, y;
		cin>>m>>n>>x>>y;
		x--;
		y--;
        // m * n 까지 하는 이유는 종말의 해가 m과 n의 최소공배수인데
        // 최소공배수는 m * n 보다 크거나 같다.
        // 그래서 그냥 m * n을 해줬다.
		for(int k = x; k < (m * n); k += m) {
			if(k % n == y) {
				flag = true;
				cout<<k + 1<<"\n"; // 처음에 -1을 해줬으므로
				break;
			}
		}
		if(!flag) cout<<"-1\n"; 
	}
}