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

• 問題
• AC
• AC (累積和)

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

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

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

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

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

想定解とか

TBE

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

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

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

SBCL メモ

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

---

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

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