백준 6064 [C++]

www.acmicpc.net/problem/6064

6064번: 카잉 달력

1. 풀이방법

 - M과N이 최대 4000씩입니다. 완전탐색의 경우 시간초과가 뜹니다

 

 - 멸망의 날 --> 이건 예시가 힌트를 주고 있는데 (10,12) 의 경우 60년이 종말의 년도 입니다

 

 - (두 수의 최소공배수)라는 게 잘 보이는 예시라서 금방 찾을 수 있었습니다.

 

 - 어떻게 해야 하나 고민을 하다가 x와y 는 문제에서 보면 M,N으로 증가율?이 나와있고 정해져 있으므로

 

 - <a,b>라고 할때 a나 b 중 하나를 x나 y 로 고정시켜도 증가율을 알고 있으므로 1씩 증가하며 탐색 시키지 않아도 

 

 - 알 수 있으므로 하나를 고정 시킵니다.

 

 

 

2. 주의사항

 - N을 넘어갈 때 0으로 초기화 되지 않고 1부터 초기화 되서 시작하므로

 

   (mod연산의 경우 0~N-1) 이므로 신경써서 MOD연산을 계산합니다

 

 

 

3. 나의코드

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

int T, M, N, x, y;

int GCD(int num1, int num2) { //최대 공약수
	if (num1%num2 == 0) return num2;
	return GCD(num2, num1%num2);
}
int LCM(int num1,int num2){ //최소 공배수
	return (num1*num2) / GCD(num1, num2);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	while (T--) {
		cin >> M >> N >> x >> y;
		int resultyear = x;
		bool check = false;
		while (1) {
			if (resultyear > LCM(M, N)) { break; }
			if (((resultyear-1)% N) +1 == y) { check = true; break; }
			resultyear += M;
		}
		if (check == true) { cout << resultyear << "\n"; }
		else { cout << -1 << "\n"; }
	}
	return 0;
}