[BOJ 32594 // C++] Kangaroo Race

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 32594번 문제인 Kangaroo Race이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/32594

 

캥거루가 \(x\)에 있을 때, 한 번 움직인 뒤에 캥거루가 있게 되는 곳은 \(x^2\)과 같다는 점을 관찰하자. (\(n\)보다 크다면 그렇지 않게 될 때까지 \(n\)을 빼는 것을 반복한다.\)

 

\(n\)과 \(x\)가 공통 소인수 \(g\)를 가진다면 아무리 이동해도 \(x\)는 g의 배수가 되므로 \(x\)는 1이 될 수 없다. 이 뒤로는 \(n\)과 \(x\)가 공통 소인수를 갖지 않는 경우(즉, 서로소인 경우)만을 생각한다.

 

\(x\)에 있는 캥거루가 이동을 \(r\)번 하면 있게 되는 위치는 \(\mod n\)에 대하여 \(x^{2^r}\)과 합동이다. 따라서 문제의 조건을 만족하려면 \(2^r\)은 \(x\)의 위수(order)의 배수여야 한다. 따라서, 라그랑주 정리(Lagrange's Theorem)를 같이 이용하면 \(n\) 미만의 2의 거듭제곱 형태의 수가 \(x\)의 위수인지 판단하는 것으로 문제를 충분히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll gcd(ll x, ll y) {
	if (y) return gcd(y, x % y);
	return x;
}

ll AA, BB; lll A, B;

void solve() {
	cin >> AA >> BB;
	if (gcd(AA, BB) > 1) {
		cout << "impossible\n";
		return;
	}
	int ans = 0;
	A = AA, B = BB;
	for (int k = 0; k < 100; k++) {
		if (B == 1) {
			cout << ans << '\n';
			return;
		}
		B = B * B % A;
		ans++;
	}
	cout << "impossible\n";
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) solve();
}