結果

問題 No.1884 Sequence
ユーザー gew1fw
提出日時 2025-06-12 16:01:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,317 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 133,792 KB
最終ジャッジ日時 2025-06-12 16:01:59
合計ジャッジ時間 11,247 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 5 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from math import gcd

def get_divisors(g):
    divisors = set()
    if g == 0:
        return divisors
    for i in range(1, int(math.isqrt(g)) + 1):
        if g % i == 0:
            divisors.add(i)
            divisors.add(g // i)
    return sorted(divisors)

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

s = [x for x in a if x != 0]

if not s:
    print("Yes")
    sys.exit()

if all(x == s[0] for x in s):
    print("Yes")
    sys.exit()

s_sorted = sorted(s)
diffs = []
for i in range(1, len(s_sorted)):
    diffs.append(s_sorted[i] - s_sorted[i-1])

if not diffs:
    print("No")
    sys.exit()

current_gcd = 0
for d in diffs:
    current_gcd = math.gcd(current_gcd, d)

if current_gcd == 0:
    print("No")
    sys.exit()

divisors = get_divisors(current_gcd)

s_min = s_sorted[0]
s_max = s_sorted[-1]

for d in divisors:
    remainder = s_min % d
    valid = True
    for x in s_sorted:
        if x % d != remainder:
            valid = False
            break
    if not valid:
        continue
    
    if (s_max - s_min) % d != 0:
        continue
    m = (s_max - s_min) // d
    
    max_k1 = (n - 1) - m
    max_k2 = (s_min - 1) // d
    max_k = min(max_k1, max_k2)
    
    if max_k >= 0:
        print("Yes")
        sys.exit()

print("No")
0