結果

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

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    S = [x for x in A if x > 0]
    m = len(S)
    
    if m == 0:
        print("Yes")
        return
    if m == 1:
        print("Yes")
        return
    
    sorted_S = sorted(S)
    differences = []
    for i in range(m-1):
        diff = sorted_S[i+1] - sorted_S[i]
        differences.append(diff)
    
    g = differences[0]
    for diff in differences[1:]:
        g = math.gcd(g, diff)
    
    if g == 0:
        print("Yes")
        return
    
    def get_divisors(g_val):
        if g_val == 0:
            return []
        divisors = set()
        for i in range(1, int(math.isqrt(g_val)) + 1):
            if g_val % i == 0:
                divisors.add(i)
                divisors.add(g_val // i)
        return sorted(divisors)
    
    divisors = get_divisors(g)
    
    for d in divisors:
        if d == 0:
            continue
        r = sorted_S[0] % d
        valid = True
        for x in sorted_S:
            if x % d != r:
                valid = False
                break
        if not valid:
            continue
        
        max_low = -float('inf')
        for x in sorted_S:
            current = x - (N-1)*d
            if current > max_low:
                max_low = current
        
        min_x = sorted_S[0]
        lower = max(max_low, 1)
        upper = min_x
        
        if lower > upper:
            continue
        
        if r > upper:
            continue
        
        if r >= lower:
            a_candidate = r
        else:
            k = (lower - r + d - 1) // d
            a_candidate = r + k * d
        
        if a_candidate > upper:
            continue
        
        print("Yes")
        return
    
    print("No")

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