[백준] 6064 카잉 달력 [자바]

 

 

---

https://mygumi.tistory.com/325

백준 6064번 카잉 달력 :: 마이구미

※ 종말의 해는 최소공배수(최소 공배수를 넘어가면 -1 출력)

※ x를 고정하고 y를 바꾼다.

  1. x만큼 해를 증가시킨다 <x:x> -> 뒤의 x가 == y라면 x출력(count = x, tempy = x)

  2. 다음 해도 x를 만들기 위해서는 N만큼 증가시켜야 된다.(x+N N을 넘어가면 1로 바뀌기 때문, count = x+N, y는 N만큼 증가한 해에서 M을 넘어가면 1로 바뀌기 때문에 y = x+N % M -> tempy % M이 == y 라면 출력 아니라면 tempy += N)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			int N = Integer.parseInt(st.nextToken());
 			int M = Integer.parseInt(st.nextToken());
 			int x = Integer.parseInt(st.nextToken());
 			int y = Integer.parseInt(st.nextToken());
 			int lcm = N*M;
 			if(N > M) {
 				lcm /= gcd(N,M);
 			}
 			else {
 				lcm /= gcd(M,N);
 			}
 			int cnt = x % (N+1);
 			int tempy = x;
 			
 			for(int i = 0; i < M; i++) {
 				int ty = tempy % M == 0 ? M : tempy % M;
 				if(ty == y) {
 					break;
 				}
 				tempy = ty + N;
 				cnt += N;
 			}
 			if(cnt > lcm) {
 				System.out.println(-1);
 			}
 			else {
 				System.out.println(cnt);
 			}
 		}
 	}
 	static int gcd(int a, int b) {
 		while(b != 0) {
 			int r = a % b;
 			a = b;
 			b = r;
 		}
 		return a;
 	}
}