G - Divisible by 3 解説
by 
MMNMM
このユーザ解説は執筆中です。書かれていない部分や不正確な記述がある場合があります。ご了承ください。
zhoukangyang さんの記事の内容をもとに、この問題を \(\tilde O(\sqrt N)\) 時間で解く解法を解説します。
公式解説および kyopro_friends さんの解説の内容を前提とします。
本解説では、特別に断らない場合、数列 \(f,g\colon\mathbb N\to K\) に対して \(fg\) のように書いたとき、それらの Dirichlet 積 \(\displaystyle (fg)(n)=\sum _ {ij=n}f(i)g(j)\) を表すこととします。 また、\(f\colon\mathbb N\to K\) と非負整数 \(n\) に対して \(f ^ n\) と書いたとき、 Dirichlet 積の単位元 \(e(x)=\begin{cases}1&(x=0)\\0&(\text{otherwise})\end{cases}\) に対して \(f\) を \(n\) 回かけたものとします。
準備 1. Dirichlet 積のアルゴリズム
まず下準備として、次の問題を解くことを考えます。
正整数 \(N\) と数列 \(f,g\colon\mathbb N\to K\) に対して、\(Q _ N\) に含まれる値までの累積和 \[F _ x=\sum _ {n=1} ^ xf(n)\quad(x\in Q _ N)\] および \[G _ x=\sum _ {n=1} ^ xg(n)\quad(x\in Q _ N)\] の値が与えられる。
\(f,g\) の Dirichlet 積に対する \(Q _ N\) に含まれる値までの累積和 \[\mathit{FG} _ x=\sum _ {n=1} ^ x(fg)(n)\quad(x\in Q _ N)\] の値を全て求めよ。
これは、maspy さんの記事 Dirichlet 積と、数論関数の累積和の中で \(O(N ^ {3/ 4})\) 時間で求める方法や追加の情報を用いて \(O(N ^ {2/ 3}(\log N) ^ {1/ 3})\) 時間で求める方法が紹介されています。
ここでは、\(K\) の要素からなる長さ \(L\) の列どうしの畳み込みが \(O(L\log L)\) 時間でできるする仮定のもとで、\(O(\sqrt N(\log N) ^ 2)\) 時間で答えを求めます。
全体の計算量を \(O(\sqrt N\operatorname{polylog}(N))\) とするために用いられているアルゴリズムですが、Dirichlet 積を求めるアルゴリズムを所与のものとして残りの解説を読むこともできるので、具体的なアルゴリズムの説明は折りたたみにしておきます。
Dirichlet 積を \(O(\sqrt N(\log N) ^ 2)\) 時間で求める（執筆中です）
\(f(i)g(j)\) を \((i,j)\) によって \(4\) つの部分に分けてそれぞれの寄与を計算します。
- \(ij\leq\sqrt N\) の部分
- \(i\gt\sqrt N\) の部分
- \(j\gt\sqrt N\) の部分
- \(i\leq\sqrt N,j\leq\sqrt N,ij\gt\sqrt N\) の部分
1, 2, 3 はそれぞれ以下のようにして寄与を計算することができます。
- 条件を満たす \((i,j)\) は \(O(\sqrt N\log N)\) 個しかなく、自然に列挙することができます。これを用いて寄与を \(O(\sqrt N\log N)\) 時間で計算できます。
- \(xy\leq\sqrt N\) なる正整数の組 \((x,y)\) を列挙して、それぞれに対して \(\dfrac N{(x+1)y}\lt i\leq\dfrac N{xy},j=y\) なる部分の寄与を計算することで \(O(\sqrt N\log N)\) 時間で 1 の部分の寄与が計算できます。
- 1 と同様に、\(i=x,\dfrac N{x(y+1)}\lt j\leq\dfrac N{xy}\) の部分の寄与を計算すればよいです。
4 の部分の寄与について考えます。
正実数 \(B\) について、\(\displaystyle L _ f(x)=\sum _ {i=1} ^ {\lfloor\sqrt N\rfloor}f(i)x ^ {\lceil B\log i\rceil},L _ g(x)=\sum _ {j=1} ^ {\lfloor\sqrt N\rfloor}g(j)x ^ {\lceil B\log j\rceil}\) を作ることを考えます。 これらはたかだか \(\left\lceil B\log\sqrt N\right\rceil\) 次式なので、\(O(B\log N(\log B+\log\log N))\) 時間で \[L(x)=\sum _ {1\leq i,j\leq\sqrt N}f(i)g(j)x ^ {\lceil B\log i\rceil+\lceil B\log j\rceil}\] を求めることができます。
求めたいものは、\(\max\left\lbrace x\in\mathbb N\mathrel{}\middle|\mathrel{}ij\leq\dfrac Nx\right\rbrace\) が等しいような \((i,j)\) にわたる \(f(i)g(j)\) の和でした。
\(B,i,j,N,x\) は正なので、\(ij\leq\dfrac Nx\iff B\log i+B\log j\leq B\log N-B\log x\) です。 ここで、\(S _ {i,j}=\left\lbrace x\in\mathbb N\mathrel{}\middle|\mathrel{}B\log i+B\log j\leq B\log N-B\log x\right\rbrace\) ではなく \(\bar S _ {i,j}=\left\lbrace x\in\mathbb N\mathrel{}\middle|\mathrel{}\lceil B\log i\rceil+\lceil B\log j\rceil\leq B\log N-B\log x\right\rbrace\) を使った場合について考えてみます。
この \(2\) つの集合が異なるときは、\(B\log i+B\log j\leq B\log N-B\log x\lt\lceil B\log i\rceil+\lceil B\log j\rceil\) を満たすような正整数 \(x\) が存在するときです。
天井関数の性質から、このような \(i,j,x\) について \(B\log i+B\log j\leq B\log N-B\log x\lt B\log i+B\log j+2\) が成り立ちます。
これを変形すると \(N\mathrm{e} ^ {-2/B}\lt ijx\leq N\) が得られ、このような \((i,j,x)\) の個数は \(O(N(1-\mathrm e ^ {-2/B})(\log N) ^ 2+N ^ {43/ 96+\varepsilon})\) 個と評価できます。
\(B=\sqrt N\) のようにとることで、個数を \(O(\sqrt N(\log N) ^ 2)\) 個とした上で、畳み込みにかかる時間を \(O(\sqrt N(\log N) ^ 2)\) 時間とすることができます。
（浮動小数点数を用いて計算を行う場合は対数などの計算において誤差が生じますが、上の議論の \(2\) の部分を \(2+2 ^ {-50}\) などに置き換えることで正しい評価を得ることができます。結論はほとんど変わりません。）
（執筆中です）
準備 2. Powerful Number の寄与の調節
\(2\) つの乗法的関数 \(f,g\) が、すべての素数 \(p\) に対して \(f(p)=g(p)\) を満たしており、\(p,e\) を与えることで \(f(p ^ e),g(p ^ e)\) を高速に求められるとします。 このような \(f,g\) に対して、\[F _ x=\sum _ {n=1} ^ xf(n)\quad(x\in Q _ N)\] の情報から \[G _ x=\sum _ {n=1} ^ xg(n)\quad(x\in Q _ N)\] を得ることを考えます。
\(f(p)=g(p)\) が成り立っているとき、\(fh=g\) を成り立たせるような唯一の乗法的関数 \(h\) について、すべての素数 \(p\) に対して \(h(p)=0\) が成り立ちます。
\(h(p)=0\) より、\(h(x)\neq0\) であるのは \(x\) が Powerful Number であるところに限ります。 \(h\) が乗法的であるので、\(h\) を決定するには \(h(p ^ e)\ (e\geq2)\) の値をすべて求められれば十分です。
素数 \(p\) に対して形式的べき級数 \(\displaystyle f _ p(x)=\sum _ {i=0} ^ \infty f(p ^ i)x ^ i,g _ p(x)=\sum _ {i=0} ^ \infty g(p ^ i)x ^ i,h _ p(x)=\sum _ {i=0} ^ \infty h(p ^ i)x ^ i\) を考えます。 このとき \(f _ ph _ p=g _ p\) が成り立ち、求めたいものは \(h _ p\) の先頭 \(\lfloor\log _ pN\rfloor\) 次だったのでひとつの \(p\) あたり \(O(\log N\log\log N)\) 時間や \(O\bigl((\log N) ^ 2\bigr)\) 時間などで \(h(p ^ e)\) の値を得ることができます。 \(p\leq\sqrt N\) なる素数 \(p\) は \(O\left(\dfrac{\sqrt N}{\log N}\right)\) 個なので、\(h(p ^ e)\) の値をすべて求めるのは \(O(\sqrt N\log N)\) 時間などで可能です。
これらをもとに \(h\) の Powerful Number における値をすべて特定することができます。
\(fh=g\) だったので、準備 1. の問題を解くことで \(G _ x\) の情報をすべて得ることができます。
本編
この問題は、乗法的関数 \(f\colon\mathbb N\to K\) の累積和 \(\displaystyle \sum _ {i=1} ^ Nf(i)\) を求めることができれば解くことができます。
いま、素数 \(p\) および正整数 \(e\) に対して、\(p,e\) を与えることで \(f(p ^ e)\) の値を高速に得ることができるとします。
次の \(3\) つのステップに分けてこの問題を解きます。
- すべての素数 \(p\) に対して \(\displaystyle f(p)=\sum _ ih _ i(p)k _ i\) が成り立ち、\(x\in Q _ N\) に対する \(\displaystyle\sum _ {n=1} ^ xh _ i(n)\) の値および素数 \(p,\) 正整数 \(e\) に対する \(h _ i(p ^ e)\) の値を高速に求めることができるような乗法的関数の族 \((h _ i) _ i\) および \(K\) の値の列 \((k _ i) _ i\) を作る。
- 各 \(i\) に対して \(H _ i\colon Q _ n\to K\) を \(\displaystyle H _ i(n)=\sum _ {p\in\mathbb P,p\leq n}h _ i(p)\) として定め、これを求める。
- 2. の結果をもとに \(F _ {\mathrm{prime}}\colon Q _ n\to K\) を求め、これを用いて \(F(N)\) を計算する。
1. 性質のいい乗法的関数に分解する
1 つめのパートは問題固有の考察が必要な場合が多いです。
今回の問題では \(3\) つの乗法的関数 \[\begin{aligned}h _ 1(n)&=1\\h _ 2(n)&=\begin{cases}0&(n\equiv0\pmod3)\\1&(\text{otherwise})\end{cases}\\h _ 3(n)&=\begin{cases}0&(n\equiv0\pmod3)\\1&(n\equiv1\pmod3)\\-1&(\text{otherwise})\end{cases}\end{aligned}\] を用いて、\(g\) は \((h _ 1),(k _ 1=M)\) について、\(h\) は \((h _ 1,h _ 2,h _ 3),(k_1=M,k _ 2=-M/2,k _ 3=M/2)\) について処理を行うことで答えを得ることができます。
それぞれ、累積和は \(\displaystyle\sum _ {i=1} ^ nh _ 1(i)=n,\sum _ {i=1} ^ nh _ 2(i)=n-\lfloor n/3\rfloor,\sum _ {i=1} ^ nh _ 1(i)=\begin{cases}1&(n\equiv1\pmod3)\\0&(\text{otherwise})\end{cases}\) として高速に求めることができます。
2. 分解した乗法的関数の素数にわたる和を求める
乗法的関数 \(h\) の \(Q _ N\) の値までの累積和が得られているとします。 \(h _ {\text{prime}}\) を \(h _ {\text{prime}}(n)=\begin{cases}h(n)&(n\in\mathbb P)\\0&(\text{otherwise})\end{cases}\) として定めます。
いま、\(\displaystyle\exp h _ {\text{prime}}=\sum _ {i=0} ^ \infty\dfrac{{h _ {\text{prime}}} ^ i}{i!}\) を考えると、\(\exp h _ {\text{prime}}\) は乗法的関数であって \((\exp h _ {\text{prime}})(p)=h(p)\ (p\in\mathbb P)\) が成り立つことがわかります（\((\exp h _ {\text{prime}})(n)\) の値を \(n\) の素因数分解を用いて表すことで確かめることができます）。
\((\exp h _ {\text{prime}})(p ^ e)=\dfrac{h(p) ^ e}{e!}\) なので、階乗を前計算しておくことでこの値は高速に求めることができます。 準備 2 の内容を用いることで、\(1\) 回の Dirichlet 積の計算で \(\exp h _ {\text{prime}}\) の \(Q _ N\) の値までの累積和を得ることができます。
乗法的関数 \(f\) に対して、\(\displaystyle\ln f=\sum _ {i=1} ^ \infty\dfrac{(1-f) ^ i}{i}\) を考えると、これは上の \(\exp\) の逆になっていることを確認できます（詳細は省略します）。 ただし、\(1-f\) は\((1-f)(1)=1-f(1),(1-f)(n)=-f(n)\ (n\gt1)\) として定められる関数とします。
\(f\) は乗法的であったので、\((1-f)(1)=0\) です。 ここから、\((1-f) ^ {\lfloor\log _ 2N\rfloor+1}\) は \(1\leq n\leq N\) のすべてに対して値が \(0\) になります。
よって、上の総和は \(1\leq i\leq\lfloor\log _ 2N\rfloor\) に制限しても構いません。 よって、\(\lfloor\log _ 2N\rfloor\) 回の Dirichlet 積の計算で \(\exp h _ {\text{prime}}\) から \(h _ {\text{prime}}\) に変換することができます。
以上より、このパートは \(h\) ひとつあたり \(O(\sqrt N(\log N) ^ 3)\) 時間となります。
3. 求める関数の素数にわたる和から答えを求める
これは \(\exp\) を求めたのち Powerful Number の寄与を修正することでできます。
このパートの時間計算量も \(O(\sqrt N(\log N) ^ 3)\) となります。
以上より、乗法的関数 \(f\) の \(N\) までの和を \(O(\sqrt N(\log N) ^ 3)\) 時間で得ることができました（ただし、ステップ 1 で得た乗法的関数の族の大きさを定数としています）。
（実装例は執筆中です。解説中のアルゴリズムを実装したら非常に遅かった（\(\log\) が \(3\) つついているので遅い）ので IOI2024中国国家集训队 论文集やnegiizhaoさんの記事に書いてある高速化パートを読んでいます）
投稿日時:
最終更新: