ABC254D - Together Square

考え方

$N$以下の整数を，平方数で割れるだけ割ったもので分類する．

同じクラスに属する数どおしを掛け合わせたときにだけ，積が平方数になる．

回答例

N = int(input())

cnt = [0] * (N + 1)
for i in range(1, N + 1):
    j = 2
    while j * j <= i:
        while i % (j * j) == 0:
            i //= (j * j)
        j += 1
    cnt[i] += 1

ans = 0
for c in cnt:
    ans += c * c

print(ans)

【参考】
【解説 実況】ABC254 AからD【かつっぱ】 - YouTube（Submission #32215745 - AtCoder Beginner Contest 254）
Editorial - AtCoder Beginner Contest 254