結果

問題 No.1884 Sequence
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:42:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,656 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 147,204 KB
最終ジャッジ日時 2025-04-16 15:45:38
合計ジャッジ時間 11,936 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 5 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def get_all_divisors(n):
    if n == 0:
        return []
    divisors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
        i += 1
    return sorted(divisors)

def compute_gcd(arr):
    current_gcd = arr[0]
    for num in arr[1:]:
        current_gcd = math.gcd(current_gcd, num)
    return current_gcd

def solve():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    known = [x for x in A if x > 0]
    m = len(known)
    if m == 0:
        print("Yes")
        return
    if m == 1:
        print("Yes")
        return
    
    sorted_known = sorted(known)
    s0 = sorted_known[0]
    sm = sorted_known[-1]
    
    if s0 == sm:
        print("Yes")
        return
    
    diffs = []
    for i in range(m-1):
        diffs.append(sorted_known[i+1] - sorted_known[i])
    g = compute_gcd(diffs)
    
    if g == 0:
        print("Yes")
        return
    
    divisors = get_all_divisors(g)
    
    for d in divisors:
        if d <= 0:
            continue
        valid = True
        for s in sorted_known:
            if (s - s0) % d != 0:
                valid = False
                break
        if not valid:
            continue
        
        steps = (sm - s0) // d
        if steps + 1 > N:
            continue
        
        required = N - steps - 1
        if required < 0:
            continue
        
        max_x = min(required, (s0 - 1) // d)
        if max_x >= 0:
            print("Yes")
            return
    
    print("No")

if __name__ == "__main__":
    solve()
0