結果
問題 | No.937 Ultra Sword |
ユーザー |
|
提出日時 | 2019-11-30 15:05:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 174 ms / 3,000 ms |
コード長 | 524 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 91,556 KB |
最終ジャッジ日時 | 2024-11-21 03:23:16 |
合計ジャッジ時間 | 8,547 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
from functools import reduce N = int(input()) A = list(map(int, input().split())) lg = [0] * (1 << 17) for i in range(1, 1 << 17): lg[i] = lg[i >> 1] + 1 def gcd(x, y): while y != 0: if x < y: x, y = y, x else: k = lg[x] - lg[y] x ^= y << k return x g = reduce(gcd, A) f = [0] * 100001 for x in A: f[x] += x souwa = sum(A) ans = 10**100 for i in range(1, 100001): s = sum(f[j] for j in range(i, 100001, i)) if gcd(i, g) == g: ans = min(ans, souwa - s + s // i) print(ans)