2019年7月9日火曜日

第3回 ドワンゴからの挑戦状 本戦 B - ニワンゴくんの約数

第3回 ドワンゴからの挑戦状 本戦 B - ニワンゴくんの約数

区間[l,r)[l, r)の約数の数がわかっているとき、区間[l,r+1),[l,r1)[l, r+1), [l, r-1)等について約数の数を求めるのは比較的容易なので、Moのアルゴリズムを使う。具体的な伸縮操作は、以下のようにする。

xlxl+1...xr1x_l x_{l+1} ... x_{r-1}の素因数分解をp1e1...pkekp_1^{e_1}...p_k^{e_k}、約数の総数をDD (=(e1+1)...(ek+1))(= (e_1+1)...(e_k+1))とし、新たにxr:=p1δ1...pkδkx_r := p_1^{\delta_1}...p_k^{\delta_k}を掛けた時の約数の総数を求めたい。このとき、いちいち新しい総数(e1+δ1+1)...(ek+δk+1)(e_1+\delta_1+1)...(e^k+\delta_k+1)を再計算する必要はない。例えばp1δ1p_1^{\delta_1}を掛けると、約数の総数はD(e1+1)1(e1+δ1+1)D \cdot (e_1+1)^{-1} (e_1 + \delta_1 + 1)に変わるので、xrx_rの素因数として現れる素数だけ扱えばよい。区間を縮小する場合も同様である。

計算量について。xix_iの素因数の種類がもっとも多くなるのはxix_i素数階乗の場合で、prime omega functionの記事によればこのとき素因数の種類はlogxi/loglogxi\sim \log x_i / \log \log x_iらしい。また、snukeさんの記事によるとMoのアルゴリズムの伸縮の総数はO(NQ){\mathcal O}(N\sqrt{Q})なので、X=maxixiX = \max_i x_iとすると全体の計算量はO(NQlogX/loglogX){\mathcal O}(N \sqrt{Q} \cdot \log X / \log \log X)

TLが2.5秒なのでこれで間に合ってほしいところだが、けっこうぎりぎりだった。以下は細かい部分。

  • xix_iの素因数分解のテーブルは事前に作っておく。この際、素数のリストから素朴に試し割りする方法は遅いので、いわゆるosa_k法を使う。O(NlogX){\mathcal O}(N \log X)
  • 逆元の計算も含むので、事前にmod  109+7\mod 10^9 + 7での逆元のテーブルを作っておく。1 ひとつのxix_iにつき、同じ素因数は高々log2105=16\lfloor \log_2 10^5 \rfloor = 16しか増えないので、1610516 \cdot 10^5までの逆元がわかればよい。オーダーで書くとO(XlogX){\mathcal O}(X\log X)
  • Moのアルゴリズムは偶数番目ブロック/奇数番目ブロックでクエリの右端の昇順/降順になるようにソートすると定数倍がかなり良くなる。ei1333さんの記事 の「その 1: 定数倍改善」に載っている。

想定解とか

TBE

素因数として2だけ、あるいは2,、3だけ除外して事前に累積和をとって扱うと、伸縮操作が軽くなって速くなる。

もっと大胆に、X\sqrt{X}までの素数を累積和で扱ってよいらしい。 この場合、各xix_iX\sqrt{X}より大きい素因数を高々1つしか持たないので、伸縮操作がO(1){\mathcal O}(1)になる。X\sqrt{X}までの素数の数がX/logX\sqrt{X}/\log Xくらいだから、累積和のテーブルを作る事前処理にO(NX/logX){\mathcal O}(N\sqrt{X}/\log X)かかり、クエリで累積和を処理するのにO(QX/logX){\mathcal O}(Q \sqrt{X}/\log X)かかる。全体の計算量はO(NQ+(N+Q)X/logX){\mathcal O}(N\sqrt{Q} + (N+Q)\sqrt{X}/ \log X)。確かにこちらのほうがよさそう。

ただ、実際にはX\sqrt{X}よりも小さい数にとどめたほうが速いようだった。一般化して、X1/αX^{1/\alpha} (α1)(\alpha \ge 1)までの素数を累積和で扱うことにする。各xix_iX1/αX^{1/\alpha}より大きい素因数を高々α1\alpha - 1種類しか持たないので、伸縮操作はO(α){\mathcal O}(\alpha)になる。X1/αX^{1/\alpha}までの素数の数がX1/α/logXX^{1/\alpha}/\log Xくらいだから、累積和のテーブルを作る事前処理にO(NX1/α/logX){\mathcal O}(NX^{1/\alpha}/\log X)かかり、クエリで累積和を処理するのにO(QX1/α/logX){\mathcal O}(Q X^{1/\alpha}/\log X)かかる。全体の計算量はO(αNQ+(N+Q)X1/α/logX){\mathcal O}(\alpha N\sqrt{Q} + (N+Q)X^{1/\alpha}/ \log X)。定数がわからないとα\alphaの最適値も決まらなそう。2

SBCL メモ

  • SBCLのdestructuring-bindが遅い問題はある程度認識していたのだが、AtCoderの古いSBCL(1.1.14)ではさらに顕著に遅いらしく、TLEする原因の1つになっていた。1.2.14でいちおう解決したってことでいいのかな。それなら7月の言語更新でSBCLの最新版が入れば問題なさそう。

  1. drkenさんの記事O(n){\mathcal O}(n)で作る方法が載っている。 ↩︎

  2. というか、X1/αX^{1/\alpha}より大きい素因数が高々α1\alpha - 1種類しかないというのは上界の粗い評価であって、ジャストではなさそう。α\alphaを大きくしても、上で与えたlogX/loglogX\log X / \log \log Xに近づくわけではないし…… ↩︎