CodeIQ「フィズバズエクストリーム問題」に提出したコード

問題

codeiq.jp

以下の正の整数のうち、

3, 5, 7, 11, 13, 17, 19, 23, 29, 31

の少なくともどれか一つの倍数となるものの総和を求めてください。

提出したコード

rubyです。

def sum(n, x)
  x * n * (n + 1) / 2
end

def f(n)
  list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
  i = (1 << list.size)-1
  s = 0

  while (i > 0) do
    k = 0
    x = 1
    a = -1

    while ( (i >> k) > 0 ) do
      if (i >> k) & 1 == 1
        x *= list[k]
        a *= -1
      end
      k += 1
    end
    
    s += sum((n / x).floor, x) * a
    i -= 1
  end
  s
end

p f(10 ** 5)
p f(10 ** 9)

方針

等差数列の和の公式を使えばいい事はすぐに分かるけど、各素数の倍数の数列をそのまま足したのでは共通部分(3の倍数の数列と5の倍数の数列なら15の倍数の数列)を重複して加算してしまうからこれをいい感じに足したり引いたりして修正する。
コードをいろいろこねくり回してたら、奇数個の素数を掛け合わせた数(3とか3*5*7とか)の倍数の時は加算して、偶数個の素数を掛け合わせた数(3*5とか3*5*7*11とか)の倍数の時は減算すればいい具合になった。

何故なのかは最終的によくわからなかったけど、フィードバックによると包除原理というそのものズバリな原理があるらしい。(もう少し早く知りたかった)
包除原理 - Wikipedia

あとは素数の組み合わせをビットを使って表現してループを回して計算するだけ。
これでループ回数が回から回まで短縮できる。(素数の数のみに依存するようになる)

実行時間はうちの環境で、何も考えずに回ループさせたら1時間ちょっとくらい。上のコードだと0.5秒くらいだった。

他に挑戦された方の回答

自分は解くだけで精いっぱいだったけど、ゴルフしてる方もいるそうです。
数行で書いてるのは凄すぎる。togetter.com