테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Kangaroo Race ======

===== 풀이 =====
  * 점프 규칙이 y에 있을때 y(y-1)만큼 앞으로 뛴다고 적혀있는데, 이 말은 곧 y에서 y^2으로 뛴다는 의미이다
  * 그러면 캥거루는 y => y^2 => y^4 => y^8 => ... => y^(2^x) 순서로 이동하게 된다. 이 값중에, n으로 나눈 나머지가 1이 되는 가장 작은 x를 찾으면 된다.
  * 우선 관련된 정수론적 지식을 정리해보면
    * 오일러의 정리에 의해서, y와 n이 서로소이면, y^Φ(n)≡1 (mod n) 이다.
    * y^x≡1 (mod n) 을 만족시키는 가장 작은 x를 y의 위수, ord(y)라 부르고, x|Φ(n) 을 만족한다.
  * 결국 2^k 가 ord(y)의 배수가 되는 가장 작은 k를 찾는 문제가 되고, 2^k가 ord(y)의 배수라면, ord(y)도 2^m 꼴이어야만 하므로, 그냥 ord(y) 가 2의 거듭제곱인지만 확인해보면 된다.
  * 이것을 진짜로 위수를 먼저 계산해서 형태를 확인할 필요는 없고, 그냥 가능성이 있는 모든 k에 대해서 위수가 되는지를 확인해보면 된다. 즉, k번 점프해보면서 나머지가 1이 되는지 확인해보고, 그 중에서 나머지를 1이 되는 경우가 없다면 그냥 impossible을 출력하면 된다.
  * 2^k가 위수가 될 가능성이 있으려면, 위수는 Φ(n)이하이므로, 2^k<= Φ(n)이어야 한다. 그리고, 오일러 피 함수를 구할 필요도 없는 것이, Φ(n)<=n 이므로 그냥 2^k<=n 인 k에 대해서만 확인해봐도 된다.
  * 결국 총 시간복잡도는 O(logn)이다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 32594. Kangaroo Race".

- Problem link: https://www.acmicpc.net/problem/32594
- Solution link: http://www.teferi.net/ps/problems/boj/32594

Tags: [math]
"""

import sys


def main():
    k = int(sys.stdin.readline())
    for _ in range(k):
        n, x = [int(x) for x in sys.stdin.readline().split()]

        if x == 1:
            print('0')
            continue

        answer = next(
            (i for i in range(1, n.bit_length() + 1) if (x := x * x % n) == 1),
            None,
        )
        print('impossible' if answer is None else answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}