結果

問題 No.1538 引きこもりさんは引き算が得意。
ユーザー lam6er
提出日時 2025-04-16 00:53:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,263 bytes
コンパイル時間 244 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 87,136 KB
最終ジャッジ日時 2025-04-16 00:55:20
合計ジャッジ時間 3,944 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 3 TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from itertools import combinations

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N

    if K in A:
        print("Yes")
        return

    current_gcd = abs(A[0])
    for num in A[1:]:
        current_gcd = math.gcd(current_gcd, abs(num))
        if current_gcd == 0:
            break

    if current_gcd == 0:
        if K == 0:
            print("Yes")
        else:
            print("No")
        return

    if K % current_gcd != 0:
        print("No")
        return

    visited = set(A)
    prev_size = 0
    while True:
        if K in visited:
            print("Yes")
            return
        current_size = len(visited)
        if current_size == prev_size:
            break
        prev_size = current_size
        new_elements = set()
        for a, b in combinations(visited, 2):
            diff1 = a - b
            diff2 = b - a
            if diff1 not in visited:
                new_elements.add(diff1)
            if diff2 not in visited:
                new_elements.add(diff2)
        visited.update(new_elements)

    print("No")

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