codeiq.jp
問題は以下のような感じ
\(10^9\) 以下の正の整数のうち、
3, 5, 7, 11, 13, 17, 19, 23, 29, 31
の少なくともどれか一つの倍数となるものの総和を求めてください。
愚直に\(10^9\)までのすべての正の整数について一つ一つ割れるか確認しているとなかなか終わらない
包除原理と等差数列の総和の公式を使えば、どの数字以下までチェックするかはあまり影響しなくなる
包除原理 - Wikipedia
import itertools, operator N = 10**9 p = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31] ret = 0 for i in xrange(len(p)): for j in itertools.combinations(p, i + 1): m = reduce(operator.mul, j) d = N / m ret += d * (d + 1) / 2 * m * (2 * (len(j) % 2) - 1) print ret
↓工夫すると7,80文字ぐらいで解けるようになるらしい！
