ABC292C - Four Variables

考え方

$1\leq n \leq N$を満たす$n$の約数はそれぞれ$O(\sqrt{n})$で求められる（Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました）．よって，$1\leq n \leq N$なるすべての$n$に対して約数を調べる計算量は$O(N\sqrt{N})$で抑えられる．

$AB$を$1\sim N$に対して全て調べるとき，

• $A, B$は$AB$の約数の組
• $C, D$は$N - AB$の約数の組

が条件を満たすものである．

回答例

約数の組$(x, y)$が$x \neq y$なら，$A, B = (x, y), (y, x)$の2通りあるが，$x=y$なら$A, B = (x, y = x)$の1通りであることに注意する．

N = int(input())
ans = 0

memo = {}
for n in range(1, N):
    i = 1
    tmp = set()
    while i * i <= n:
        if n % i == 0:
            tmp.add((i, n // i))
        i += 1
    memo[n] = tmp

num = {n:0 for n in range(1, N)}
for n in range(1, N):
    tmp = memo[n]
    for x, y in tmp:
        if x != y:
            num[n] += 2
        else:
            num[n] += 1

for AB in range(1, N):
    ans += num[AB] * num[N - AB]

print(ans)