ABCでもよく見る典型がいくつか組み合わさった問題。
自然な形で上手く組み合わさっているので、気付くとなかなか気持ちいい。
1人1人が受け取るピースの塊を、「分け前」と呼ぶことにする。
円形のケーキじゃなくて両端があるなら、大枠は典型90問の第1問目でも名高いこの問題に近くなる。
両端が分かっている場合、「全体を、$K$ 個以上の、質量 $x$ 以上の分け前に分割できるか？」が解ければ、$x$ を二分探索することで解ける。
これは端から「ピースの質量合計が $x$ 以上になったらそこですぐ切る」ことを繰り返せば、$O(N)$ で判定できる。
ただ、今回は端が決まっていないので、切り目 $1$ から切った場合は無理でも、他の切り目から始めたら行けるかもしれない。
i 1 2 3 4 5 K=3 A 6 8 6 4 3 x=8 は可能? 1から始めると、i=1,2 / 3,4 /（残りは8に満たない）で2個。NG 2から始めると、i=2 / 3,4 / 5,1 3個に分けられる。OK
$N$ 箇所全ての切り目から1回 $O(N)$ の判定を試すのは $O(N^2)$ で無理。
ただ、どこから始めても、その過程で「$i$ が分け前の開始ピースとなったら、どこまで続いて、次に切られるのはどこ」という関係性は変わらない。
例えば、上例では $i=3$ から始まった分け前は、共通して $3,4$ まで続き、次の分け前は $i=5$ から開始される。
分け前が $i$ から始まった場合の次の分け前の開始点を $x=8,i=3$ に対して $B_8[3]=5$ というように表現すると、$B_8=(3,3,5,7,7)$ となる。（1周を超える分でも番号は継続するとして）
すると $x$ を固定した場合の、各 $i$ に対する判定問題は 「$i$ を $B_x[i]$ に置き換える操作を $K$ 回行って、 最終的な $i$ が1周以内（＝$i+N$ 以下）に収まっていればよい」ということになる。
これはダブリングで高速化でき、全ての $i=1～N$ に対して $O(N \log{K})$ で求められる。
実装上のテクニックとして、OutOfIndex にならないよう $B_x$ は2周分+さらに末尾に $2N+1$ を追加しておき、
遷移後の値が $2N+1$ を超える場合は $2N+1$ で上限を切るとよい。
ダブリング中、$2N+1$ を超えそうになったら $2N+1$ でループするようになる。
1周以内に収まっているかの判定の最大値が $i=N$ から始まったときの「$2N$ 以下か？」であり、
$2N+1$ まで行ったらどの $i$ に対してもNGであることが確定するので、それ以上の具体的な値の情報は必要ない。
判定問題を満たす $i$ が1つでもある最大の $x$ が、答えの1つめ。
改めてダブリングによる $K$ 回遷移後の $i$ を求め、 1周以内に収まっていない $i$ の個数が答えの2つめ「そこで切ったら最大値を達成できない切り目」の個数となる。
「乗法的関数のPrefix-Sum」という手法を用いる。知らないと無理。知ってても本番中に考察して応用して実装するのは厳しい。
$x=p_1^{e_1}p_2^{e_2}...$ と素因数分解できるとき、 約数の総和は $(1+p_1+p_1^2+...+p_1^{e_1})(1+p_2+p_2^2+...+p_2^{e_2})...$ で求められる。
この $(1+p+p^2+...+p^e)$ というパートは、
となり、少なくともどれか1つの素因数とその指数 ($p_i, e_i)$ で $(1+p_i+p_i^2+...+p_i^{e_i})$ が3の倍数となってくれれば、$x$ は「良い整数」となる。
この判定法を用いて、$x=1～N$ に対し $x$ が良い整数である時のみ以下の問題を解くと、その総和が答えとなる。
これは $x$ の素因数毎に独立に考えることができて、例えば $x=360=2^33^25^1$ を例に取ると、
これらの積で、${}_3\mathrm{H}_M \times {}_2\mathrm{H}_M \times {}_1\mathrm{H}_M$ で求められる。
だが、これは当然、$x$ を最大 $10^{10}$ 個 調べないといけないので、TLE。
正整数を引数に取る関数 $f(x)$ が次の条件を満たすとき、$f(x)$ は乗法的関数（Multiplicative Function）であるという。
上記の通り、「$g(x):=$ 総積が $x$ となるような、長さ $M$ の数列の個数」は、乗法的関数である。
このような乗法的関数の1から $N$ までの総和 $\displaystyle F(N)=\sum_{x=1}^{N}g(x)$ は、 後述するが高速に計算する手法がある。
今回は「良い整数」のみについて $g(x)$ を足し合わせないといけないので そのままは適用できないが、工夫すれば適用できるようになる。
まずは、良い整数の要素は除いて、$F(N)$ を求めることを考える。
特殊な $N$ 頂点の木でDPをするアルゴリズム。
N=25 ①
,-----------------,-'`----,--,--,--,--,--,
② ③ ⑤ ⑦ ⑪ ⑬ ⑲ ㉓
,--'`--,--,--,--, /`,--, ｜
④ ⑥ ⑩ ⑭ ㉒ ⑨ ⑮ ㉑ ㉕
/`,--, ｜
⑧ ⑫ ⑳ ⑱
/\
⑯㉔
以下、$\mathrm{Lpf}(x):=x$ の最大の素因数 とする。
親から子への視点で整理すると、 頂点 $v$ は「$\mathrm{Lpf}(v) ～ \lfloor \frac{N}{v} \rfloor$」の間の素数を $v$ にそれぞれかけた番号の子を持つ。
仮に（$N$ が大きいので実際には無理だが）$N$ 以下の全ての素数 $p=2,3,5,...$ につき $g(p)$ が計算済みであり、 累積和を取ることで、任意の区間の「素数のみの $g(p)$ の和」が $O(1)$ で求められるとする。
すると、乗法的関数の性質「互いに素なら、$g(ab)=g(a)g(b)$」を利用すると、 たとえば②の子④⑥⑩⑭㉒（それぞれ2に2,3,5,7,11がかけられた数）のうち、
これは、$v=$ ③や⑧など、他の内部ノード（葉以外の頂点）でも $G$ を使って同様のことが言え、
という処理を全ての内部ノードについて行うことで、$x=1～N$ の全ての $g(x)$ の総和が求められることになる。
葉ノードは個別処理する必要が無い、というのがこのアルゴリズムの肝となる。
で、実際にこの木において内部ノードの数は少なく、$N=10^{10}$ に対して $6.3 \times 10^6$ 程度で済むらしい。
これで、「$G$：ある区間の素数だけの $g(x)$ の和」が求められれば、現実的な時間で $F(N)$ を求められることがわかった。
肝心の $G$ をどうやって求めるか。
$N \le 10^{10}$ のような制約で、$N$ 以下の全ての素数に対して $g(p)$ なんて求められない。
よく考えると、Black Algorithm の過程で実際に必要とされる $G(l,r)$ の $l,r$ の値って、実はそんなに多くない。
内部ノード $x$ の処理を考えるとき、必要となる $l,r$ は
$l$ の値の範囲は $r$ に内包されるので、結局、$Q(N)$ に含まれる各数 $q_i$ について $F_{\mathrm{prime}}(q_i)$ が求められれば、 Black Algorithm の過程で必要な $G(l,r)$ に対して全て答えられるということになる。
で、乗法的関数においてこれをするのがLucy DPとなる。
今回は、良い整数だけを数えなければならない。
Black Algorithm で $x$ の子の $g(*)$ をまとめて足し上げる時に、
よって、$G$ に加えて「$H(l,r):=l$ より大きく $r$ 以下の、3で割って2余る素数のみの $g(p)$ の総和」があれば、 良い整数に限定した数え上げも可能となる。
$H$ は、Lucy DPで「素数全体」に加え 「3で割って1余る素数の個数」「3で割って2余る素数の個数」に分けて管理していくと、上手く計算できる。
Black Algorithm 上でDFSをするにあたり、
などを持ちながらおこなうとよい。