結果
問題 |
No.1036 Make One With GCD 2
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:42:18 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 867 bytes |
コンパイル時間 | 241 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 175,312 KB |
最終ジャッジ日時 | 2025-06-12 15:42:43 |
合計ジャッジ時間 | 19,066 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 TLE * 1 -- * 6 |
ソースコード
import sys import math def main(): n, *rest = map(int, sys.stdin.read().split()) A = rest[:n] result = 0 current_gcds = {} for num in A: temp_gcds = {} # 添加单独的num if num in temp_gcds: temp_gcds[num] += 1 else: temp_gcds[num] = 1 # 遍历current_gcds中的每个键 for g in current_gcds: new_g = math.gcd(g, num) if new_g in temp_gcds: temp_gcds[new_g] += current_gcds[g] else: temp_gcds[new_g] = current_gcds[g] # 检查是否有GCD为1的情况 if 1 in temp_gcds: result += temp_gcds[1] # 更新current_gcds为temp_gcds current_gcds = temp_gcds.copy() print(result) if __name__ == "__main__": main()