結果

問題 No.937 Ultra Sword
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:02:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,784 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 81,712 KB
実行使用メモリ 99,296 KB
最終ジャッジ日時 2025-04-15 22:04:07
合計ジャッジ時間 5,586 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    sum_original = sum(A)
    
    if N == 0:
        print(0)
        return
    
    max_a = max(A)
    cnt = [0] * (max_a + 2)
    for a in A:
        cnt[a] += 1
    
    # Compute prefix sum
    prefix = [0] * (max_a + 2)
    prefix[0] = cnt[0]
    for v in range(1, max_a + 1):
        prefix[v] = prefix[v - 1] + cnt[v]
    
    # Precompute sum_div_x for all x from 1 to max_a
    sum_div_x = [0] * (max_a + 1)
    for x in range(1, max_a + 1):
        total = 0
        k = 0
        while True:
            start = k * x
            if start > max_a:
                break
            end = (k + 1) * x - 1
            end = min(end, max_a)
            if start == 0:
                count = prefix[end]
            else:
                count = prefix[end] - prefix[start - 1]
            total += k * count
            k += 1
        sum_div_x[x] = total
    
    # Compute GCD of A
    G = A[0]
    for a in A[1:]:
        G = math.gcd(G, a)
    
    # Compute minimal sum using Ultra Sword on original monsters
    min_ultra_original = float('inf')
    for a in A:
        if G % a != 0:
            continue
        s = sum_div_x[a]
        if s < min_ultra_original:
            min_ultra_original = s
    
    # Compute B and check if any pair XOR to 1
    B = [a // G for a in A]
    b_set = set(B)
    found = False
    for x in B:
        if (x ^ 1) in b_set:
            found = True
            break
    
    sum_gcd = sum(B) if found else float('inf')
    
    # Compute the answer
    candidates = [sum_original, min_ultra_original, sum_gcd]
    answer = min(candidates)
    print(answer)

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