BOJ/백준-2981-python

문제📖

풀이🙏

• 첫째 줄에 종이에 적은 수의 개수 N이 주어진다.
• 다음 줄부터 N개의 줄에는 종이에 적은 수가 하나씩 주어진다.
• 같은 수가 두 번 이상 주어지지 않는다.
• 항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다,.
• 상근이는 심심하다
• 상근이는 N을 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다.
• 가능한 M을 모두 찾는 프로그램을 작성하라.
• M을 공백으로 구분하여 모두 출력하라. 이 때, M은 오름차순 정렬되어야 한다.

코드💻

# boj, 2981 : 검문, python3
# 정수론 및 조합론
import sys

def gcd(x, y):
    while y != 0:
        x,y = y,x%y
        
    return x

def solve(n, l):
    for i in range(n-1):
        l[i] = abs(l[i+1] - l[i])
    l.pop()

    number = l[0]
    
    for i in l:
        number = gcd(number, i)

    answer = set([number])

    for i in range(2, 1 + int(number**(1/2))):
        if number%i == 0:
            answer.add(i)
            answer.add(number//i)
    
    return ' '.join(map(str, sorted(answer)))


N = int(sys.stdin.readline())
l = [int(sys.stdin.readline()) for _ in range(N)]

print(solve(N, l))

결과😎

출처 && 깃허브📝

https://www.acmicpc.net/problem/2981
github