結果

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

ソースコード

diff # 

import sys
import math
from math import gcd
from functools import reduce
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    # Compute GCD of all elements
    def compute_gcd(arr):
        return reduce(lambda x, y: gcd(x, y), arr)
    G = compute_gcd(A)
    
    # Compute sum_gcd
    sum_gcd = sum(a // G for a in A)
    
    # Compute total_sum
    total_sum = sum(A)
    
    # Precompute div_sum
    def get_divisors(a):
        divisors = set()
        for i in range(1, int(math.isqrt(a)) + 1):
            if a % i == 0:
                divisors.add(i)
                divisors.add(a // i)
        return divisors
    
    div_sum = defaultdict(int)
    for a in A:
        divisors = get_divisors(a)
        for d in divisors:
            div_sum[d] += (a - (a // d))
    
    # Compute sum_sword
    sum_sword = float('inf')
    unique_x = list(set(A))  # Process unique elements to avoid duplicates
    for x in unique_x:
        current = total_sum - div_sum.get(x, 0)
        if current < sum_sword:
            sum_sword = current
    
    # Check if G can be created via XOR of two elements
    s = set(A)
    can_create_g = any( (a ^ G) in s for a in s )
    
    # Determine the answer
    answer = total_sum  # Original sum
    if can_create_g:
        answer = min(answer, sum_gcd)
    answer = min(answer, sum_sword)
    
    print(answer)

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