사용자 도구

사이트 도구


ps:problems:boj:32594

Kangaroo Race

ps
링크acmicpc.net/…
출처BOJ
문제 번호32594
문제명Kangaroo Race
레벨골드 3
분류

수학

시간복잡도O(T*logn)
인풋사이즈T<=10^5, n<=10^18
사용한 언어Python 3.11
제출기록31120KB / 1264ms
최고기록1264ms
해결날짜2024/11/01

풀이

  • 점프 규칙이 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)이다

코드

"""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()

토론

댓글을 입력하세요:
N F​ S F Q
 
ps/problems/boj/32594.txt · 마지막으로 수정됨: 2024/11/04 07:20 저자 teferi