結果
| 問題 | No.1262 グラフを作ろう！ |
| ユーザー |
 zkou
|
| 提出日時 | 2020-10-16 22:56:40 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,915 bytes |
| コンパイル時間 | 192 ms |
| コンパイル使用メモリ | 82,360 KB |
| 実行使用メモリ | 214,960 KB |
| 最終ジャッジ日時 | 2024-07-20 23:24:31 |
| 合計ジャッジ時間 | 12,227 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
ソースコード
from functools import lru_cache
# 与えられた N 以下の素数を列挙して、その N 以下の素数の素因数分解を高速に与えるアルゴリズム。
#
# 計算量:
# 構築: O(N)
# 素因数分解: n <= N なる n に対し O(log n)、N < n <= N**2 なる n に対し、O(N / log N)
#
#
# 参考: https://cp-algorithms.com/algebra/prime-sieve-linear.html (n <= N に対して O(log n) の部分)
N = 10 ** 6 + 10 # 10 ** 7 以下だとよさそう。10 ** 7 でPyPy3で構築に500ms程度。
lp = [0] * (N+1)
pr = [] # N 以下の素数のリスト
for i in range(2, N+1):
if lp[i] == 0:
lp[i] = i
pr.append(i)
for j, p in enumerate(pr):
if p > lp[i] or i * p > N:
break
lp[i * p] = p
def fac_small(n):
"""
引数 n の素因数分解をして、素因数を昇順に格納したリストを返す。
ex. fac_small(60) == [2, 2, 3, 5]
与えられた n について 1 <= n <= N を仮定する。n == 1 では空リストを返す。
計算量は O(log n)
"""
# assert 1 <= n <= N
ret = []
while n > 1:
ret.append(lp[n])
n //= lp[n]
return ret
def fac(n):
"""
引数 n の素因数分解をして、素因数を昇順に格納したリストを返す。
ex. fac_small(60) == [2, 2, 3, 5]
与えられた n について 1 <= n <= N**2 を仮定する。n == 1 では空リストを返す。
計算量は、1 <= n <= N で O(log n)、N < n <= N ** 2 で O(N / log N) 程度。
"""
# assert 1 <= n <= N**2
if 1 <= n <= N:
return fac_small(n)
else:
sqr = int(N ** 0.5) + 10
ret = []
for p in pr:
while n % p == 0:
n //= p
ret.append(p)
if n == 1:
return ret
elif n <= N:
return ret + fac_small(n)
if p > sqr:
break
ret.append(n)
return ret
from collections import Counter
from itertools import product
def enumerate_factors(ls):
c = Counter(ls)
iterators = [[k**i for i in range(v + 1)] for k, v in c.items()]
ret = []
for tup in product(*iterators):
t = 1
for x in tup:
t *= x
ret.append(t)
return ret
@lru_cache
def solve(A):
ls = fac_small(A)
facs = enumerate_factors(ls)
facs.sort()
ps = list(set(ls))
dic = {f: A // f for f in facs}
for p in ps:
for f in facs:
if A % (f * p) == 0:
dic[f] -= dic[f * p]
# print(dic)
return sum((f * c for f, c in dic.items()))
N, M = map(int, input().split())
As = list(map(int, input().split()))
ans = 0
for A in As:
ans += solve(A) - A
# if solve(A) != sum((gcd(i, A) for i in range(1, A + 1))):
# print(A, solve(A), sum((gcd(i, A) for i in range(1, A + 1))))
print(ans)