Educational Codeforces Round 12 F. Four Divisors

大体は Editorial に書いてある方法だと思います。

1 から n までの整数のうち約数をちょうど 4 つ持つものは何個あるか。

約数が 4 つある整数は p³ か pq の形である。p³ であるようなものは O(n^1/3) で数え上げられるので、pq の数え上げ方だけを考えよう。

p<q とすれば p≦√n まで考えればよく、各 p に対して P(n/p) が高速に求められればこの問題は解ける。P(n) は 1 から n に含まれる素数の個数。

P(n) を求めるために以下のような DP を行う。

√n 以下の p[i] で割り切れない n 以下の整数は素数になるので、P(n)=dp[n][j]+j-1 が成り立つ。ただし p[j]>√n。

またこれを逆手に取ることで p[j]＞√n のとき dp[n][j]+j-1=dp[n][j+d]+j+d-1 が成り立つことも分かる。

さて漸化式を立てていこう。

j=0 のときは特に制限がないので dp[n][0]=n が成り立つ。

p[0]..p[j-1] で割り切れない整数というのは、以下の 2 つのケースがある。

前者の個数は dp[n][j+1] 個である。後者の個数は K が p[0]..p[j-1] で割り切れない n/p[j] 以下の整数であることから dp[n/p[j]][j] 個になる。したがって次の関係が成り立つ。

$$ dp[n][j] = dp[n][j+1] + dp[n/p[j]][j] $$

この式を少し変形すると次の式になる。

$$ dp[n][j]=dp[n][j-1]-dp[n/p[j-1]][j-1] $$

これを愚直に計算させると間に合わないが、n が小さいときは別の方法を取るようにすればギリギリ間に合う。

n が小さいときは区間総和セグメント木を永続化させたもので計算した。7986 ms。

本番ではまーすさんのライブラリをお借りして解いた。計算量がよくわからないけど間に合ってるので満足。