kingsubin

import java.io.*;
import java.util.StringTokenizer;

public class boj_6064 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            boolean isOk = false;
            for (int j = x; j < m*n; j+=m) {
                if (j % n == y) {
                    System.out.println(j+1);
                    isOk = true;
                    break;
                }
            }

            if (!isOk) System.out.println(-1);
        }

    }
}

 

생각

- 날짜 계산의 문제와 유사하게 1부터 쭉 반복문을 돌려가며 찾을려고 생각했음

- 근데 m,n의 범위가 각각 4만이라서 O(N^2)의 풀이의 경우 시간초과

- 풀이가 생각이 안나면 손으로 하나씩 적어보자

 

풀이

- 숫자를 적어나가다 보면 나머지 규칙이 있음

- x, y 값 중 하나를 고정 시키고 그 값의 범위만큼 널뛰기 하면 나머지 하나의 값만 변하게 되고

  계속 반복하다 보면 언젠간 나오게 되어있음

- 풀이에서는 초기값을 x에 고정시키고 여기서 x의 범위인 m만큼 널뛰기하면 x값은 고정이고

   j % n == y를 만족할때까지 반복하면 됨

- 초기에 x, y를 -1씩 해줘야 나머지가 딱 맞게 떨어질 수 있음

- 출력시에는 처음에 뺏으니 +1 해준다