結果

問題 No.1917 LCMST
コンテスト
ユーザー lam6er
提出日時 2025-04-16 01:02:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,394 bytes
コンパイル時間 512 ms
コンパイル使用メモリ 81,948 KB
実行使用メモリ 254,340 KB
最終ジャッジ日時 2025-04-16 01:05:26
合計ジャッジ時間 24,574 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    A.sort()
    if n == 0:
        print(0)
        return
    min_val = A[0]
    max_A = 10**5  # 根据题目中的A_i的最大可能值设置
    
    # 预处理每个数的因数列表，按降序排列
    factors = [[] for _ in range(max_A + 1)]
    for d in range(1, max_A + 1):
        for x in range(2 * d, max_A + 1, d):
            factors[x].append(d)
    # 对每个数的因数列表按降序排序
    for x in range(1, max_A + 1):
        factors[x].sort(reverse=True)
    
    # 使用存在数组来记录已经存在的数
    exist = [False] * (max_A + 1)
    exist[min_val] = True
    sum_total = 0
    
    for i in range(1, n):
        x = A[i]
        found = False
        # 遍历x的因数列表（降序）
        for d in factors[x]:
            if d > x:
                continue  # 确保因数d确实小于x，理论上不会有这种情况
            if exist[d]:
                sum_total += x
                found = True
                break
        if not found:
            # 计算LCM(min_val, x)
            g = math.gcd(min_val, x)
            lcm = min_val * x // g
            sum_total += lcm
        # 标记当前数存在
        exist[x] = True
    
    print(sum_total)

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