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 より簡単な気がする。