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;
	}
}