ABC249D - Index Trio

考え方

エラトステネスの篩-likeな考え方で解ける．
AtCoder - 解法パターンの整理 - 競プロはじめました

以下のループは$O(N \log N)$であることがポイント．

for i in range(N):
  for j in range(i, N + 1, i):
    # 処理

回答例

from collections import defaultdict

N = int(input())
A = sorted(list(map(int, input().split())))

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1

ans = 0
for a in A:
    for i in range(a, A[-1] + 1, a):
        if i in cnt and i // a in cnt:
            ans += cnt[i] * cnt[i // a]

print(ans)