結果
問題 | No.1730 GCD on Blackboard in yukicoder |
ユーザー | customfolk |
提出日時 | 2021-11-12 18:20:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,686 bytes |
コンパイル時間 | 795 ms |
コンパイル使用メモリ | 87,512 KB |
実行使用メモリ | 123,608 KB |
最終ジャッジ日時 | 2023-08-07 23:39:18 |
合計ジャッジ時間 | 9,715 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 303 ms
120,116 KB |
testcase_01 | AC | 223 ms
94,384 KB |
testcase_02 | AC | 221 ms
94,392 KB |
testcase_03 | AC | 238 ms
94,200 KB |
testcase_04 | AC | 237 ms
94,372 KB |
testcase_05 | AC | 221 ms
94,160 KB |
testcase_06 | AC | 234 ms
94,288 KB |
testcase_07 | AC | 233 ms
94,228 KB |
testcase_08 | AC | 219 ms
94,140 KB |
testcase_09 | AC | 229 ms
94,420 KB |
testcase_10 | AC | 232 ms
94,168 KB |
testcase_11 | AC | 216 ms
94,448 KB |
testcase_12 | AC | 217 ms
94,348 KB |
testcase_13 | AC | 292 ms
120,276 KB |
testcase_14 | AC | 293 ms
120,256 KB |
testcase_15 | AC | 296 ms
119,960 KB |
testcase_16 | AC | 299 ms
119,880 KB |
testcase_17 | AC | 302 ms
120,244 KB |
testcase_18 | AC | 296 ms
119,724 KB |
testcase_19 | AC | 295 ms
120,020 KB |
testcase_20 | AC | 298 ms
123,608 KB |
testcase_21 | AC | 298 ms
123,400 KB |
testcase_22 | AC | 296 ms
119,728 KB |
testcase_23 | AC | 280 ms
122,108 KB |
testcase_24 | AC | 289 ms
121,872 KB |
testcase_25 | AC | 294 ms
119,624 KB |
ソースコード
from collections import defaultdict, deque, Counter from heapq import heapify, heappop, heappush import math from copy import deepcopy from itertools import combinations, permutations, product, combinations_with_replacement from bisect import bisect_left, bisect_right import sys def input(): return sys.stdin.readline().rstrip() def getN(): return int(input()) def getNM(): return map(int, input().split()) def getList(): return list(map(int, input().split())) def getListGraph(): return list(map(lambda x:int(x) - 1, input().split())) def getArray(intn): return [int(input()) for i in range(intn)] mod = 10 ** 9 + 7 MOD = 998244353 sys.setrecursionlimit(10000000) inf = float('inf') eps = 10 ** (-15) dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] ############# # Main Code # ############# """ 1個消した時、2個消した時...のgcdの最大 連続性はないので、 これは何の約数になるか? [0, 3, 3, 2, 2, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 値が1以上のものについての最大値 2以上のものについての最大値... """ N = getN() cnt = [0] * (10 ** 6 + 7) # 数字の個数 for a in getList(): cnt[a] += 1 # multi[i]: iの倍数が何個あるか # 1個以上あれば、 multi = [0] * (10 ** 6 + 7) for i in range(1, 10 ** 6 + 7): # i * 1, i * 2...について数えていく for j in range(i, 10 ** 6 + 7, i): multi[i] += cnt[j] ans = [] # 逆から探索 # i個以上のものについての値の最大 for i in range(10 ** 6 + 6, -1, -1): # multi[i] == len(ans)になるまで while multi[i] > len(ans): ans.append(i) for a in ans[::-1]: print(a)