結果

問題 No.937 Ultra Sword
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:47:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,512 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 81,996 KB
実行使用メモリ 90,660 KB
最終ジャッジ日時 2025-04-16 15:48:47
合計ジャッジ時間 5,252 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    # Compute GCD of all elements
    G = A[0]
    for num in A[1:]:
        G = math.gcd(G, num)
    
    # Check if sum_g is achievable
    a = [num // G for num in A]
    sum_g = sum(a)
    has_G = G in A
    
    found_xor_1 = False
    if not has_G:
        seen = set()
        for num in a:
            target = num ^ 1
            if target in seen:
                found_xor_1 = True
                break
            seen.add(num)
    sum_g_achievable = has_G or found_xor_1
    
    # Compute sum_sword_min
    max_A = max(A) if A else 0
    freq = [0] * (max_A + 1)
    for num in A:
        freq[num] += 1
    sum_total = sum(A)
    
    # Precompute sum_divisible for all possible d
    sum_divisible = [0] * (max_A + 1)
    for d in range(1, max_A + 1):
        k = 1
        while d * k <= max_A:
            sum_divisible[d] += k * freq[d * k]
            k += 1
    
    sum_sword_min = float('inf')
    for x in A:
        d = x
        current_sum = 1 + sum_total - sum_divisible[d] * (d - 1)
        if freq[d] > 0:
            current_sum -= 1
        if current_sum < sum_sword_min:
            sum_sword_min = current_sum
    
    sum_original = sum_total
    candidates = [sum_original, sum_sword_min]
    if sum_g_achievable:
        candidates.append(sum_g)
    
    answer = min(candidates)
    print(answer)

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