TopCoder SRM 691 (Div. 2) Hard. Undiv2

問題

k の約数ではない 2 番目に小さい正の整数を S(k) とする。S(1)+S(2)+...+S(n) を求めよ。

  • 1≦n≦109

解法

f(i, j) を次の条件を満たす 1..n の数の個数とする。

  • 1..i-1 で割り切れる
  • i で割り切れない
  • i+1..j-1 で割り切れる
  • j で割り切れない

もしこれが求まれば、

$$ \sum_{i<j} f(i,j) \cdot j $$

で答えが得られる。1..100 で割り切れる数なんてのは 109 以下には存在しないので、考えるべき i,j は 100 以下で良い。

後は f(i,j) を高速に計算できれば OK。f(i,j) の条件が若干見づらいので、以下のように文字を置いて整理しよう。

  • L=LCM(1,2,3,...,i-1,i+1,i+2,...,j-1)
  • A: L で割り切れる数の集合
  • B: i で割り切れる数の集合
  • C: j で割り切れる数の集合

こうすると f(i,j) は次のように表せる。

$$ f(i,j)=|A \cap \overline{B} \cap \overline{C}|=|A|-|A \cap B|-|A \cap C| + |A \cap B \cap C| $$

最後の式変形は包除原理を使った。包除原理が分からなくてもベン図で OK。

1..n の整数のうち k の倍数は $\lfloor n/k \rfloor$ 個である。このことを使えば f(i,j) も高速に計算できる。


i,j≦100 はあくまで計算量の見積もりの話で、実際は 109 をオーバーしたらループを終えるようにした方がオーバーフローしなくて安心。

med より簡単な気がする。