白駿2981号「尋問」

5691 ワード
アルゴリズム#アルゴリズム# テキストリンク

質問する


白駿2981号尋問。

に答える


昇順の入力値a,bを受け取ると、aとbの最小公約数に関する式が以下のようにまとめられる.

このことから,b−aはa,bの最小公約数の倍数であることが分かる.
また、残りのRを同一にする数字Mについてまとめると、以下のようになる.

b−aはa,bの最大公約倍数であるため,mはa,bの最大公約数の倍数/公約数であることがわかる.
すなわち,入力した数字を昇順に並べ替え,隣接数の車の最大承諾数を求め,その数の約数を求める.

Pythonコード

import sys
import math
input = sys.stdin.readline

n = int(input())
num = []
for _ in range(n):
  num.append(int(input()))

num.sort()

arr = []
for i in range(1, n):
  arr.append(num[i]-num[i-1])

tmp = arr[0]
for i in range(len(arr)):
  tmp = math.gcd(tmp, arr[i])

ans = [tmp]
for i in range(2, int(tmp**0.5)+1):
  if tmp % i == 0:
    ans.append(i)
    ans.append(tmp//i)

ans.sort()
ans = list(set(ans))

for x in ans:
  print(x, end=' ')
[react]共通フォルダの画像を使用する
[PyLv 1]シーザーパスワード