1. ๋ฌธ์ ์ค๋ช
< M:N >์ด๋ ๋ฌ๋ ฅ์ด ์๋๋ฐ, (x,y) -> (1,1) , (2,2) ๊ฐ๋ค๊ฐ x๊ฐ M์ ๋๊ฑฐ๋, y๊ฐ N์ ๋์ผ๋ฉด ๋ค์ 1๋ก ๋์์จ๋ค.
์์ ์ ์ค๋ช
๋์ด ์๋ ๋๋ก, <10,12> ์ผ๋, 13๋ฒ์งธ ๋
๋๋ <3,1>์ด ๋๋ค. <10,10> , <1,11>, <2,12>, <3,1> ์์ผ๋ก ์จ๋ค.
๋ฌธ์ ์์ M,N,x,y๋ฅผ ์ค ๋, <M,N> ๋ฌ๋ ฅ์์ <x,y>๊ฐ ๋ช ๋ฒ์งธ ๋ ๋์ธ์ง ๊ตฌํ๋ผ.
2. ์ ๊ทผ ๋ฐฉ์
์ด๊ฒ๋ ๋์ ํ ์๊ฐ์ด ์๋์ ๋ค๋ฅธ ์ฌ๋ ํ์ด ๋ดค๋ค. (์์ฆ ์ ์ด๋ ๊ฒ ํ์ด๊ฐ ์๊ฐ์ด ์๋์ง? ๋ ์ด์ฌํ ํด์ผ๊ฒ ๋ค.)KEY WORD
: ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ
, LCM๊ณผ GCD์ ๊ด๊ณ
๋จผ์ <1,1> ~ <M,N>๊น์ง ์์๋๋ก ๋ฒํธ๋ฅผ ๋งค๊ธด๋ค๊ณ ํด๋ณด์. ์ด๋ ์ฐ๋ฆฌ๊ฐ ๊ตฌํด์ผํ๋ <x,y>๋ K๋ฒ์งธ ์๋ผ๊ณ ํด๋ณด์.
x๋ K๋ฅผ M์ผ๋ก ๋๋์์ ๋์ ๋๋จธ์ง์ด๊ณ , y๋ K๋ฅผ N์ผ๋ก ๋๋์์ ๋ ๋๋จธ์ง ์ด๋ค.
<10,12>์์ <3,9>๋ 33๋ฒ์งธ ์์ธ๋ฐ, 33%10 = 3, 33%12 = 9 ์์ ์ ์ ์๋ค.
์์ผ๋ก ๋ํ๋ด๋ณด๊ฒ ๋ค.
K = M * q + x
K = N * q` + y
์ฌ๊ธฐ์ M์ด ๊ณ ์ ๋์ด ์๋๋ผ๋ x๊ฐ ๋์ค๋ K๋ ์ฌ๋ฌ๊ฐ์ง์ผ ์ ์๋ค. ๊ทธ๋ ๋ค๊ณ 1๋ถํฐ ๋ชจ๋ ์๋ฅผ K์ ๋์ ํ์ฌ ๊ตฌํ๋ค๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋๋ค. ์ด๋ป๊ฒ ํด์ผํ ๊น?
๋๋จธ์ง๊ฐ x๊ฐ ๋์ค๋ K๊ฐ N์ผ๋ก ๋๋์์ ๋ y๊ฐ ๋์จ๋ค๋ฉด ์ฐ๋ฆฌ๊ฐ ์ฐพ๋ ์์ด๋ค.
๋๋จธ์ง๊ฐ x๊ฐ ๋์ค๋ ์๋ค์ ํ๋ณด๊ตฐ์ผ๋ก ๋๊ณ ๋ฌธ์ ๋ฅผ ํ๋ฉด ๋๋ฏ๋ก, q๋ฅผ ์ฌ๋ ค์ ์๊ฒฉ์ด ์๋ ์ซ์๋ค์ ๊ฑด๋๋ด๋ค.
๋ฌธ์ ์ ์์๋ก ์๋ฅผ ๋ค์ด๋ณด์.
์ฐ๋ฆฌ๋ <10,12>
์์ <3,9>
๊ฐ ๋ช๋ฒ์งธ ์์ธ์ง ์ฐพ์๋ด์ผ ํ๋ค.
๋จผ์ q = 0
์ผ๋, ์๊ฐํด๋ณด๋ฉด, K = 0+3 ์ด๋ค. ์ด๊ฒ์ N์ธ 12๋ก ๋๋๋ฉด, <3,3>
์ด ๋์จ๋ค. ๋ฐ๋ผ์ ํ๋ฝ
๋ ๋ฒ์งธ, q = 1
์ผ๋, K = 13์ด๋ค. ์ด๊ฒ์ 12๋ก ๋๋๋ฉด 1 ์ฆ <3,1>
์ด ๋์จ๋ค. ํ๋ฝ
์ธ ๋ฒ์งธ, q = 2
์ผ๋, K = 23์ด๋ค. ์ด๊ฒ์ 12๋ก ๋๋๋ฉด, <3,11>
์ด ๋์จ๋ค. ํ๋ฝ
๋ค ๋ฒ์งธ, q = 3
์ผ๋, K = 33์ด๋ค. ์ด๊ฒ์ 12๋ก ๋๋๋ฉด <3,9>
๊ฐ ๋์จ๋ค. ์ ๋ต!
โป์ฃผ์: ๋ฒ์ ์ ํ๊ธฐ
ํ์ง๋ง ๋ฌธ์ ์์๋ ์ ๋ ์นด์ ๋ฌ๋ ฅ์ ๋์ฌ ์ ์๋ ์ซ์๋ฅผ ์
๋ ฅ์ ์ค ์๋ ์๋ค. ์ด๋, ๋ฒ์๋ฅผ ์ ํด๋๊ณ ๊ณ์ฐ์ ์ํ์ง ์์ผ๋ฉด ๋ฌดํ ๋ฃจํ์ ๋น ์ง ๊ฒ์ด๋ค. ์ด๋๊น์ง ๊ณ์ฐ ํด์ผํ ๊น? ์นด์๋ฌ๋ ฅ์ Max๊ฐ์ธ <M,N> ์ ๋๋ฌํ๋ฉด ์ข
๋ง์ ๋ง์ดํ๊ณ ๋๋๋ค.
๊ทธ๋ฌ๋ฉด <M,N>์ ๊ณผ์ฐ ๋ช ๋ฒ์งธ ์์ธ๊ฐ?
<M,N>์ ์๋ฒ์ M๊ณผ N์ ์ต์๊ณต๋ฐฐ์
์ด๋ค.
์๋ํ๋ฉด, ๋ ์์ ์ํ์ด ๊ฐ์์ง๋ ์๊ฐ์ด ๋ฐ๋ก ๋์ด๊ธฐ ๋๋ฌธ์ด๋ค. <7,5>๋ฉด ๋ ์๊ฐ ๊ฐ์ด ์์ ์ ๊ฐ๋ ์๊ฐ์ 35๋ฒ์งธ ์๊ฐ์ด๋ค.
์ต์ ๊ณต๋ฐฐ์ ์ด์ผ ๊ตฌํจ?
์ฌ๊ธฐ์ ์ํ์ ์ง์์ด ์์ผ๋ฉด ํค๋งจ๋ค. ๋๋ ํค๋งค์๋ค.
๋ ์ A,B์ ์ต๋๊ณต์ฝ์๋ฅผ G๋ผ๊ณ ํ ๋, ๋๋๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๋ ๊ฒ์ด๋ค. a์ b๋ ์๋ก์์ด๋ค.
์ด๋, ์ต๋๊ณต์ฝ์ x a x b = ์ต์๊ณต๋ฐฐ์ ์ด๋ค.
๊ทธ๋ผ A,B๋ฅผ ๊ณฑํด๋ณด์. AxB= (Ga) x (Gb)
์ ๊ฐ๋ค. ์ด๊ฒ์ G๋ก ๋๋๋ฉด?
์ต์๊ณต๋ฐฐ์๊ฐ ๋์จ๋ค. ๋ฐ๋ผ์ ๋์์ ๊ณฑ / ์ต๋๊ณต์ฝ์ = ์ต์ ๊ณต๋ฐฐ์
๋ผ๋ ๊ด๊ณ๊ฐ ๋์จ๋ค. ์ด๋ฅผ ์ด์ฉํด ๋ฌธ์ ๋ฅผ ํ๋ฉด ๋๋ค.
๊ทธ๋ผ ์ต๋๊ณต์ฝ์๋ ์ด์ผ ๊ตฌํจ?
์ด๊ฑด ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ์ฐ๋ฉด ๋๋ค. ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ๊ฐ๋จํ ๋งํด์A = Bq + R
์ผ๋, A์ B์ ์ต๋๊ณต์ฝ์๋ B์ R์ ์ต๋๊ณต์ฝ์์ ๊ฐ๋ค๋ ๊ฒ์ด๋ค. ์ด๊ฒ์ ์ด์ฉํด์ ์ฐ์์ ์ผ๋ก ๋๋๋ค ๋ณด๋ฉด ์ด๋ ์๊ฐB = Rq + 0
์ ์๊ฐ์ด ์จ๋ค. ์ด๋ฌ๋ฉด R๋ B์ ์ฝ์์ด๊ณ , B์ R์ ์ต๋๊ณต์ฝ์๋ R ์์ ์ด ๋๋ค. ๊ทธ๋ ๋ค๋ฉด A,B์ ์ต๋๊ณต์ฝ์๋ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ๋ฐ๋ผ R์ด ๋๋ค.
ํ ์ค ์์ฝ
๋ฐ๋ผ์ ์ด๋ฅผ ์ด์ฉํด M๊ณผ N์ ์ต๋๊ณต์ฝ์
-> ๊ทธ๊ฑธ๋ก ๋ ์ฌ์ด์ ์ต์๊ณต๋ฐฐ์ ๊ตฌํจ
-> M*q ๊ฐ ์ต์๊ณต๋ฐฐ์๋ฅผ ๋์ง ์์ ๋๊น์ง ๋ฐ๋ณต
์ผ๋ก ๋ฒ์๋ฅผ ์ ํด์ ํ๋ฉด ๋๋ค.
3. ์ฝ๋ ๋ถ์
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int test_case = Integer.parseInt(br.readLine());
for (int t = 0; t < test_case; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 1. ์ต์ ๊ณต๋ฐฐ์ ๊ตฌํ๊ธฐ -> ์ต์ ๊ณต๋ฐฐ์๋ฅผ ๋์ด์ ๊ณ์ ๊ฐ์ ์ ์ถํ๊ณ ์์ผ๋ฉด ์ ํจํ์ง ์์ ์์์ผ๋ก -1 ์ถ๋ ฅ
int lcm = M>N? (M*N/gcd(M,N)) : (M*N/gcd(N,M));
// 2.
int ans = -1;
int n = 0;
while (n*M < lcm) {
if((n*M+x-y)%N == 0) {
ans = n*M+x;
break;
}
else n++;
}
System.out.println(ans);
}
}
public static int gcd (int A, int B) {
if(A%B == 0) return B;
else return gcd(B, A%B);
}
}
์ฌ๊ธฐ์ ์ง๊ด์ ์ผ๋ก ์ดํด๊ฐ ๋์ง ์๋ ๋ถ๋ถ์ด (n*M+x-y)%N == 0
๋ถ๋ถ์ผ ๊ฒ์ด๋ค.
n์ ์์์ ์ค๋ช
ํ q์ด๋ค.
๋ฐ๋ผ์ n*M+x
๋ K๊ฐ ๋ ์ ์๋ ํ๋ณด๊ตฐ์ด๋ค. ๋ง์ฝ n*M+x == K
๋ผ๋ฉด,K = q*N+y
๋ ๋๋ค. ๋ฐ๋ผ์,
n*M+x-y = K - y = q*N
์ด ๋๋ค.
๋ฐ๋ผ์ (n*M+x-y)%N == 0
์ด ์ฑ๋ฆฝํ๋ค๋ฉด, ์ฐ๋ฆฌ๊ฐ ์ฐพ๋ K๋ฅผ ์ฐพ์ ๊ฒ์ด ๋๋ค.