Submission #39424357

---

Source Code Expand

from collections import deque
import sys
import math

sys.setrecursionlimit(2*10**6)

array = [-1 for i in range(2*10**5)]
result = []

n = int(input())

for ab in range(1, n):
  cd = n - ab
  # ab 組み合わせ列挙
  ab_count = 0
  if array[ab] != -1:
    ab_count = array[ab]
  else:
    for i in range(1, int(math.sqrt(ab)+1)):
      if ab%i == 0:
        ab_count += 1
    ab_count *= 2
    if int(math.sqrt(ab))**2 == ab:
      ab_count -= 1
    array[ab] = ab_count

  # cd 組み合わせ列挙
  cd_count = 0
  if array[cd] != -1:
    cd_count = array[cd]
  else:
    for i in range(1, int(math.sqrt(cd)+1)):
      if cd%i == 0:
        cd_count += 1
    cd_count *= 2
    if int(math.sqrt(cd))**2 == cd:
      cd_count -= 1
    array[cd] = cd_count
  result.append(ab_count*cd_count)

print(sum((result)))

Submission Info

Judge Result