[백준] 6064번 - 카잉 달력

 

 

x와 y값 중 한 가지를 잡고 그 나머지에다가 M 또는 N값을 더한게 다른 변수의 나머지와 같으면 되게 하는 문제이다. 처음에는 M*N을 탐색하여 시간초과가 나서 최적의 값을 구하기 위해서 M과 N의 최소공배수를 구해 그 값까지만 탐색하여 문제를 해결하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p6064 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int a = Integer.parseInt(br.readLine());
		int[] rst = new int[a];
		for (int i = 0; i < a; i++) {
			rst[i] = -1;
		}
		for (int i = 0; i < a; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int M = Integer.parseInt(st.nextToken());// M
			int N = Integer.parseInt(st.nextToken());// N
			int x = Integer.parseInt(st.nextToken());// x
			int y = Integer.parseInt(st.nextToken());// y

			int k = M * N / gcd(M, N);
			for (int j = 0; j * M < k; j++) {
				System.out.println(j * M + x - y);
				if ((j * M + x - y) % N == 0) {
					rst[i] = j * M + x;
				}
			}
			System.out.println();
		}
		
		for (int i = 0; i < a; i++) {
			System.out.println(rst[i]);
		}
	}

	public static int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}
}