inamori’s diary

https://projecteuler.net/problem=29 前回は例えば2乗までのとき何個がダブるかをナイーブに数えていましたが、2乗までなら2～N/2がダブると分かるので、数えるまでもありません。6乗までだと、N/6～N/3の間は2から5の倍数はダブりますが、重複を考えると包除原理を使わないといけません。しかし、前回よりかなり速いはずです。最後のところで多倍長整数を使うとより大きいときも計算できます。でも30秒程度でした。実際のところ、が素数でないと速いです。 from collections import Dict from math import min, max, abs import sys #################### library #################### fn gcd(n: Int, m: Int) -> Int: return n