사용자 도구

사이트 도구


ps:problems:boj:2981

검문

ps
링크acmicpc.net/…
출처BOJ
문제 번호2981
문제명검문
레벨골드 5
분류

정수론

시간복잡도O(nlogm + sqrt(m))
인풋사이즈n<=100, m<=1,000,000,000
사용한 언어Python
제출기록31312KB / 76ms
최고기록56ms
해결날짜2021/10/18

풀이

  • x랑 y가 M으로 나눈 나머지가 같다면, (x-y)는 M으로 나누어 떨어진다
  • 따라서 수들을 두개씩 묶어서 차를 구한 뒤에, 그 차들의 공약수를 구하는 방식으로 M을 구할 수 있다. 모든 공약수를 구하는 방법은, 최대공약수를 구하고 그 최대공약수의 약수들을 구하는 것이다.
    • 이때 모든 n(n+1)/2 개의 페어에 대해서 모두 차를 구할 필요는 없다. 그냥 숫자들이 한번 이상씩 등장할수 있도록 n-1개의 페어만 만들어도 된다. GCD(a[1]-a[0], a[2]-a[1], …, a[n-1]-a[n-2]) 로 구하거나, GCD(a[1]-a[0], a[2]-a[0], …, a[n-1]-a[0]) 로 구하는 것이 쉽다.
  • 이렇게 최대공약수 g를 구하고 나면에 g의 약수들을 찾는 것은 1부터 sqrt(g) 까지로 나눠보면서 찾으면 된다.
  • 총 시간복잡도는 n개의 수의 gcd를 구하는 데에 O(nlogm), 구한 gcd의 약수들 구하는 데에 O(sqrt(m))이므로, O(nlogm + sqrt(m)). (m은 수의 최대값)

코드

"""Solution code for "BOJ 2981. 검문".

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

Tags: [NumberTheory]
"""

import math


def main():
    N = int(input())
    nums = [int(input()) for _ in range(N)]
    last_num = nums.pop()
    diffs = [x - last_num for x in nums]
    gcd = math.gcd(*diffs)
    small, large = [], [gcd]
    for i in range(2, math.isqrt(gcd) + 1):
        q, r = divmod(gcd, i)
        if r == 0:
            small.append(i)
            if i != q:
                large.append(q)

    print(*(small + large[::-1]))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
S I D​ E W
 
ps/problems/boj/2981.txt · 마지막으로 수정됨: 2021/10/19 17:37 저자 teferi