geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC243G Sqrt

自力AC

解をf(X)とします。

まず、\sqrt{x}以下の最大の整数は二分探索により、O(logx)で得られます。ここでは、sqrt(x)とします。

X\leq 10^6くらいの場合

dp[i]:=iが与えられた時に生成可能な数列の種類数

と定義すると、

dp[i]\leftarrow dp[1]+dp[2]+\cdots + dp[sqrt(i)]と求められます。

ここで、dpの累積和S_{dp}をとっておけば、

dp[i]\leftarrow S_{dp}[sqrt(i)]

と求められるので、sqrt(x)の計算も含め、小さい方からDPテーブルをO(XlogX)で計算できます。
なお、数列の項が1になった時点で1が延々と続くだけなので、初期値はdp[1] \leftarrow 1です。

この時の解は、f(X)=dp[X]です。

X\leq 10^{12}くらいの場合

f(X)=S_{dp}[sqrt(X)]となります。
前述した通り、10^6までのDPテーブルは計算できるので、解を得られます。

X\leq 9\times 10^{18}の場合

  • f(X)=dp[1]+dp[2]+\cdots + dp[sqrt(i)]

であり、

  • dp[i]=S_{dp}[sqrt(i)]

であるので、

  • f(X) = S_{dp}[sqrt(1)]+S_{dp}[sqrt(2)]+\cdots + S_{dp}[sqrt(sqrt(X))]

とおけます。
これより、sqrt(x)yとなる個数をg(y)とし、k=sqrt(sqrt(X))とすると、

f(X)=S_{dp}[1]\times g(1)+\cdots +S_{dp}[k-1]\times g(k-1)+S_{dp}[k]\times Z

とできます。
Zsqrt(X)以下でsqrt(x)kとなるものの数です。

g(x)は、x^2 \leq i \lt  (x+1)^2を満たすiの個数として求められます。

dp_2[i] = S_{dp}[i]\times g(i)

とすれば、O(N)でDPテーブルを計算できます。

また、S_{dp_2}dp_2の累積和とすると、

f(X)=S_{dp_2}[k-1]+S_{dp}[k]\times Z

とおけます。

後は、Zの求め方ですが、

Z=sqrt(X) - k^2 +1

で求められます。

提出コード