6064 ์นด์๋ฌ๋ ฅ
์๊ณ ๋ฆฌ์ฆ(์ํ)
1. n ์ M๊ณผ N์ผ๋ก ๋๋์์๋ ๋์จ ์๊ฐ x์ y ์ด๋ฉด ๋๋ค.
๋จ, ๋๋์์๋ ๋์ค๋ ์๋ 0~M-1 or N-1์ธ๋ฐ ๋ฌธ์ ์์ 1~M, 1~N ๊น์ง์ด๋ฏ๋ก ์ด๊ฑธ ๊ณ ๋ คํด์ผํ๋ค.
2. ํ๋์ฉ ์ฆ๊ฐ์์ผ๊ฐ๋ฉด์ํ๋ฉด ๋๋ฌด ์ค๋๊ฑธ๋ฆฌ๋, M๊ณผ N ์ค ๋ ํฐ์๋ฅผ ๋ํ๋ ์๋ก ์ผ๊ณ , ๊ทธ๊ฒ๊ณผ ์ฐ๊ฒฐ๋ ์๋ถํฐ ์์ํ๋ค(M-x, N-y)
ex) 10 12 3 4 ์ด๋ฉด 4๋ถํฐ ์์ํ์ฌ 12์ฉ ๋ํจ
๊ฐ ๋จ๊ณ์ ์๋ฅผ 10๊ณผ 12๋ก ๋๋์ด์ 3๊ณผ 4๊ฐ ๋์ค๋ฉด ๊ฐ๋ฅํ ๊ฒ.
3. ์ด๋ M๊ณผ N์ด ๊ฐ์ ๊ฒฝ์ฐ x, y์ด ๋ค๋ฅด๊ฒ ๋์ค๋ฉด ๋ฐ๋ก -1 ์ ์ถ๋ ฅํ๋๋ก ํด์ผ ํ๋ฆฌ์ง ์๋๋ค.
4. 2๋ฅผ ์ต์๊ณต๋ฐฐ์ ์ดํ์ผ๋๊น์ง๋ง ๊ฒ์ฌํ๋๋ฐ, ์ต์๊ณต๋ฐฐ์ ๊ตฌํ๊ธด ๊ท์ฐฎ์ผ๋ฏ๋ก M*N ์ดํ์ผ ๋๊น์ง ๊ฒ์ฌํ์.
์ต๋ N ๋ฒ ๊ฒ์ฌํ๋๊ฒ ๊ณ ์์ด๊ณ , N ์ ์ต๋ 4๋ง์ด๋ค. (M < N์ผ๋)
์ฝ๋
#include <iostream>
using namespace std;
int M, N, x, y;
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> M >> N >> x >> y;
int result = 0, lap, start;
if (M > N) {
lap = M;
start = x;
}
else if(M < N) {
lap = N;
start = y;
}
else if (x != y) {
cout << -1 << endl;
continue;
}
else {
lap = N;
start = y;
}
while (start <= M * N) {
int t1 = start % M == 0 ? M : start % M;
int t2 = start % N == 0 ? N : start % N;
if (t1 == x && t2 == y) {
result = start;
break;
}
start += lap;
}
if (result == 0)
cout << -1 << endl;
else
cout << result << endl;
}
}