読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

CodeIQ #フィズバズエクストリーム 問題に挑戦した

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文字ぐらいで解けるようになるらしい!

-->