結果

問題 No.1884 Sequence
ユーザー lam6er
提出日時 2025-03-20 20:43:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,895 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 152,608 KB
最終ジャッジ日時 2025-03-20 20:43:53
合計ジャッジ時間 11,774 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 5 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def input():
    return sys.stdin.read()

def is_possible(N, A):
    S = [a for a in A if a != 0]
    K = len(S)
    if K <= 1:
        return True
    S.sort()
    min_S = S[0]
    max_S = S[-1]
    # Check if all elements are the same
    if min_S == max_S:
        return True
    # Compute consecutive differences and their GCD
    diffs = []
    for i in range(1, K):
        diffs.append(S[i] - S[i-1])
    g = diffs[0]
    for d in diffs[1:]:
        g = math.gcd(g, d)
    if g == 0:
        return True
    # Generate all divisors of g
    def get_divisors(x):
        divisors = set()
        for i in range(1, int(math.isqrt(x)) + 1):
            if x % i == 0:
                divisors.add(i)
                divisors.add(x // i)
        return sorted(divisors, reverse=True)
    divisors = get_divisors(g)
    # Check each divisor
    for d in divisors:
        r = S[0] % d
        # Check if all elements in S have remainder r mod d
        valid = True
        for num in S:
            if num % d != r:
                valid = False
                break
        if not valid:
            continue
        # Check if (max_S - min_S) <= (N-1)*d
        if (max_S - min_S) > (N-1) * d:
            continue
        # Compute x0_low and x0_high
        x0_low = max(1, max_S - (N-1)*d)
        x0_high = min_S
        if x0_low > x0_high:
            continue
        # Check if there exists x0 in [x0_low, x0_high] such that x0 ≡ r mod d
        rem_want = r % d
        rem_low = x0_low % d
        delta = (rem_want - rem_low + d) % d
        candidate = x0_low + delta
        if candidate > x0_high:
            # No solution in this range
            continue
        else:
            return True
    return False

data = input().split()
N = int(data[0])
A = list(map(int, data[1:N+1]))

if is_possible(N, A):
    print("Yes")
else:
    print("No")
0