ABC 322 G — Two Kinds of Base

考察

二つの基数をすべて試すには範囲が大きすぎる。そこで、同じ桁列を二通りに評価した「差」に注目する。基数の差は与えられた差の約数に限られ、さらに各桁の重みが下位桁全体の最大寄与を上回るため、基数を固定すれば桁を高位から一つずつ確定できる。

基数の差を固定し、長さで分ける

桁列を S=(S1,…,Sk)S=(S_1,\ldots,S_k) とする。k=1k=1 ならどの基数でも値は S1S_1 なので、正の差 XX は作れない。k≥2k\geq 2 では、先頭桁が正で他の桁も非負であるため、基数を大きくすると値は厳密に増える。従って解では a>ba>b である。また b=1b=1 では全桁が0に制限され、先頭桁を正にできない。以降は a>b≥2a>b\geq 2 とし、

s=a−b,d=min⁡(10,b),De=ae−be(e≥0)s=a-b,\qquad d=\min(10,b),\qquad D_e=a^e-b^e\quad(e\geq 0)

と置く。各桁の範囲は 0,…,d−10,\ldots,d-1、差の条件は

X=∑e=0k−1Sk−eDeX=\sum_{e=0}^{k-1} S_{k-e}D_e

となる。D0=0D_0=0 なので末尾桁は差に影響しない。一方、e≥1e\geq 1 では冪差の因数分解により s∣Des\mid D_e だから、必ず s∣Xs\mid X である。大きい NN そのものを走査する代わりに、小さい XX の約数を列挙する方針が見えてくる。

まず k=2k=2 では、先頭桁を c=S1c=S_1 とすると条件は X=csX=cs だけになる。1≤c≤91\leq c\leq 9 のうち c∣Xc\mid X を満たすものを試せば、s=X/cs=X/c が決まる。先頭桁の上限と a=b+s≤Na=b+s\leq N を合わせた範囲は

L=c+1≤b≤N−s=UL=c+1\leq b\leq N-s=U

である。各 bb について末尾桁は d=min⁡(10,b)d=\min(10,b) 通りなので、L≤UL\leq U のとき

∑b=LUmin⁡(10,b)=F(U)−F(L−1)\sum_{b=L}^{U}\min(10,b)=F(U)-F(L-1)

を加える。ただし非負整数 tt に対し、

F(t)={t(t+1)/2(0≤t≤9),45+10(t−9)(t≥10)F(t)=\begin{cases} t(t+1)/2 & (0\leq t\leq 9),\\ 45+10(t-9) & (t\geq 10) \end{cases}

である。L>UL>U なら加算は0とする。これで、二桁では bb の候補が巨大でも区間和で処理できる。

次に k≥3k\geq 3 を考える。先頭桁が1以上なので X≥Dk−1≥D2X\geq D_{k-1}\geq D_2 であり、

D2=(b+s)2−b2=s(2b+s)≤XD_2=(b+s)^2-b^2=s(2b+s)\leq X

が必要になる。従って XX の約数 ss ごとに、

2≤b≤min⁡(N−s,⌊X/s−s2⌋),a=b+s2\leq b\leq \min\left(N-s,\left\lfloor\frac{X/s-s}{2}\right\rfloor\right),\qquad a=b+s

だけを列挙すればよい。上端が2未満なら候補はない。この範囲は NN が大きくても XX だけで抑えられる。残る課題は、一つの基数対について桁列をどう調べるかである。

一つの重みは下位桁全体より大きい

通常の位取り表記では、下位桁をすべて最大にしても一つ上の位に届かない。その性質が、今回の重み DeD_e にもあれば、高位から商を取る方法が使える。そこで、まず桁上限を b−1b-1 とした下位桁の最大寄与と比べる。

e≥1e\geq 1 に対して等比級数を展開すると、

ae−1=(a−1)∑i=0e−1ai,be−1=(b−1)∑i=0e−1bia^e-1=(a-1)\sum_{i=0}^{e-1}a^i,\qquad b^e-1=(b-1)\sum_{i=0}^{e-1}b^i

だから、その差を使って

De−(b−1)∑i=0e−1Di=(a−1)∑i=0e−1ai−(b−1)∑i=0e−1bi−(b−1)(∑i=0e−1ai−∑i=0e−1bi)=(a−b)∑i=0e−1ai=s∑i=0e−1ai>0\begin{aligned} &D_e-(b-1)\sum_{i=0}^{e-1}D_i\\ &\quad=(a-1)\sum_{i=0}^{e-1}a^i-(b-1)\sum_{i=0}^{e-1}b^i\\ &\qquad -(b-1)\left(\sum_{i=0}^{e-1}a^i-\sum_{i=0}^{e-1}b^i\right)\\ &\quad=(a-b)\sum_{i=0}^{e-1}a^i\\ &\quad=s\sum_{i=0}^{e-1}a^i>0 \end{aligned}

を得る。実際の上限は d−1≤b−1d-1\leq b-1 なので、

(d−1)∑i=0e−1Di≤(b−1)∑i=0e−1Di<De(d-1)\sum_{i=0}^{e-1}D_i\leq (b-1)\sum_{i=0}^{e-1}D_i<D_e

も成り立つ。b≥10b\geq 10 で桁上限が9になる場合も、同じ証明を使える。

商が桁を強制する理由

高位の桁を処理した後の残余を RR とする。残る指数が ee 以下なら、解が存在するためには

R=ceDe+T,0≤ce<d,0≤T≤(d−1)∑i=0e−1Di<DeR=c_eD_e+T,\qquad 0\leq c_e<d,\qquad 0\leq T\leq(d-1)\sum_{i=0}^{e-1}D_i<D_e

と書ける必要がある。ここで cec_e は指数 ee の桁、TT は下位桁の寄与である。従って

ce=⌊R/De⌋c_e=\left\lfloor R/D_e\right\rfloor

が強制される。商を一つ減らすと下位桁へ DeD_e 以上を渡すことになり、最大寄与を超える。商が dd 以上のときも、合法な小さい桁へ置き換えて下位桁で埋めることはできない。

具体的には、De≤XD_e\leq X を満たす最大の指数を EE とし、R=XR=X から e=E,E−1,…,1e=E,E-1,\ldots,1 の順に商を求める。どこかの商が dd 以上なら不可能、そうでなければ RR を R−ceDeR-c_eD_e に更新する。最後の残余が0なら、選んだ桁の寄与の和がちょうど XX なので十分でもある。指数0の桁で余りを埋めることはできない。

例えば a=3,b=2a=3,b=2 なら d=2d=2、重みは D1=1,D2=5,D3=19D_1=1,D_2=5,D_3=19 となる。

  • X=6X=6 では商は指数2で1、残余1、指数1で1、残余0となる。末尾を除く桁列は (1,1)(1,1) に決まり、末尾を0または1として (1,1,0),(1,1,1)(1,1,0),(1,1,1) の2通りを得る。
  • X=7X=7 では指数2の桁を1にした残余が2で、指数1の商2が桁上限に反する。指数2の桁を0にしても、下位の最大寄与は1なので救えない。

最大指数 EE より大きい桁は、1以上なら重みだけで XX を超える。一方、EE 未満の桁だけでは最大寄与が DE≤XD_E\leq X に届かない。従って解の先頭の指数は必ず EE、先頭桁は正である。三桁以上の列挙では E≥2E\geq 2 を確認し、復号に成功した基数対ごとに末尾桁の選択数 dd を加える。高々一つなのは末尾を除く桁列であり、末尾まで含む列は dd 通りある。

典型の発動条件

差の因数による候補圧縮

巨大な二つの整数について多項式評価の差が小さい値に固定されるなら、共通因子となる二整数の差を探す。本問では a−b∣Xa-b\mid X に加え、三桁以上の先頭項から二乗差の上限を得た。二桁のようにこの上限を使えない場合は分けて直接数える。

superincreasing weightのgreedy復号

各重みが「合法な下位係数による最大総和」を上回るなら、高位の商が唯一の係数になる。この性質を満たす重みを superincreasing な重みと呼ぶことがある。単に重みが増加するだけでは不十分であり、下位の最大総和との厳密な不等式を証明してから使う。

自由な零weight桁の分離

係数の重みが0なら、その係数は目標値から復元できない。他の係数を確定させた後、合法な選択数を掛ける。ただし他の制約にも影響しないことを確認する。本問の末尾桁は先頭桁ではなく、桁上限以外の制約を持たない。

問題固有の要素

同じ桁列を異なる基数で評価する条件から、冪差を重みにした表現が現れる。この重みは基数差で割り切れるだけでなく、桁上限と組み合わせると下位の最大寄与を上回る。差の因数分解で候補を減らし、残った候補内では表現の一意性を使う、という二段階を見抜くことが核心である。

正当性

k=1k=1 では差が0となる。k≥2k\geq 2 の解では、非負の桁と正の先頭桁から a>b≥2a>b\geq 2 が必要である。二桁の解は先頭桁 c∣Xc\mid X と s=X/cs=X/c、区間 c+1≤b≤N−sc+1\leq b\leq N-s の選択に一対一に対応し、末尾の選択数は min⁡(10,b)\min(10,b) である。三桁以上の解は s∣Xs\mid X かつ s(2b+s)≤Xs(2b+s)\leq X を満たすため、指定した約数と基数の列挙から漏れない。

各基数対では、De−(b−1)∑i=0e−1Di=s∑i=0e−1ai>0D_e-(b-1)\sum_{i=0}^{e-1}D_i=s\sum_{i=0}^{e-1}a^i>0 と d≤bd\leq b より、合法な下位桁の寄与は DeD_e 未満である。従って存在する解の各桁は高位から取る商に強制され、商が dd 以上なら解はない。すべての商が合法で最終残余が0なら、その桁列は差の条件を満たす。先頭の指数は DE≤X<DE+1D_E\leq X<D_{E+1} を満たす EE に限られるので、末尾を除く桁列は高々一つである。

三桁以上では E≥2E\geq 2 を要求し、自由な末尾桁の dd 通りを加える。二桁と三桁以上は重ならず、異なる基数対は別の組なので、加算結果は求める全組数となる。

実装上の注意

  • N=1N=1 や N=2N=2 では a>b≥2a>b\geq 2 を満たす対がなく、答えは0となる。列挙の下端を2とし、空区間を処理すれば自然に除外できる。
  • 答えは 998244353998244353 で割った余りを取る。二桁の区間和は64 bit整数で計算してから加算すればよい。
  • 重み DeD_e は XX 以下のものを指数1から保存し、初めて XX を超えたところで止める。等号の場合は保存する。D0=0D_0=0 では割り算せず、最後の残余と末尾の自由度を別に処理する。

冪をそれぞれ X+1X+1 に飽和させてから引いてはいけない。例えば a=3,b=2,e=3,X=19a=3,b=2,e=3,X=19 では、27−8=1927-8=19 を求めたいのに、飽和後の差は 20−8=1220-8=12 となる。代わりに、正の項だけからなる

D1=s,De+1=bDe+saeD_1=s,\qquad D_{e+1}=bD_e+s a^e

を使う。b(ae−be)+(a−b)ae=ae+1−be+1b(a^e-b^e)+(a-b)a^e=a^{e+1}-b^{e+1} なので、この漸化式は正確である。乗算前の判定まで含めた生成手順は次のようにできる。

  1. 現在の De≤XD_e\leq X と P=min⁡(ae,X+1)P=\min(a^e,X+1) を保持する。初期値は D1=sD_1=s、P=min⁡(a,X+1)P=\min(a,X+1) とする。
  2. De>⌊X/b⌋D_e>\lfloor X/b\rfloor なら次の重みは XX を超えるので停止する。そうでなければ T=bDe≤XT=bD_e\leq X を計算する。
  3. P>⌊(X−T)/s⌋P>\lfloor(X-T)/s\rfloor なら停止する。そうでなければ De+1=T+sP≤XD_{e+1}=T+sP\leq X を計算して保存する。P=X+1P=X+1 に飽和していた場合は必ず停止するため、保存する差は常に正確である。
  4. 次の反復のため、P>⌊X/a⌋P>\lfloor X/a\rfloor なら P=X+1P=X+1、そうでなければ P=aPP=aP と更新する。

これなら超過する積を実際に作らずに済む。De+1≥2DeD_{e+1}\geq 2D_e で重みは増え続けるため、一度超えた後の指数もすべて除外できる。復号は保存した重みを逆順に使い、三桁以上の処理では最大指数が2以上であることを確認する。

復習の核

  • 候補の上限が巨大でも、差が小さいなら因数分解から「差の約数」を列挙できないか考える。
  • 高位から商を取るには、下位桁の最大寄与が現在の重み未満であることを示す。単調増加や典型名だけで正当化しない。
  • 重み0の桁は一意復号の対象から外し、自由度として数える。差を計算するときも、二つの値を個別に飽和すると相殺を壊すことに注意する。

計算量と制約

時間

約数は O(X)O(\sqrt X) 時間で列挙でき、二桁の処理は先頭桁9通りで O(1)O(1) 時間である。三桁以上の基数対の総数を CC とすると、各約数 ss に対して b≤X/(2s)b\leq X/(2s) だから、

C≤∑s∣X⌊X2s⌋≤X2∑s=1X1s=O(Xlog⁡X)C\leq\sum_{s\mid X}\left\lfloor\frac{X}{2s}\right\rfloor \leq\frac X2\sum_{s=1}^{X}\frac1s =O(X\log X)

と XX だけで評価できる。各対では De+1≥2DeD_{e+1}\geq 2D_e より重みの生成と復号がともに O(log⁡X)O(\log X) 時間なので、全体は O(X+Clog⁡X)=O(Xlog⁡2X)O(\sqrt X+C\log X)=O(X\log^2 X) 時間となる。

空間

約数一覧に O(τ(X))O(\tau(X))、一つの基数対の重み列に O(log⁡X)O(\log X) を使う。ここで τ(X)\tau(X) は XX の約数の個数である。基数対や桁列をすべて保存する必要はなく、全体は O(τ(X)+log⁡X)O(\tau(X)+\log X) 空間である。

制約との対応

1≤N≤1091\leq N\leq 10^9 に対して基数対の全探索はできないが、1≤X≤2×1051\leq X\leq 2\times 10^5 なので、二桁を区間和で処理し、三桁以上の候補と重み数を XX で制限できる。時間制限は2秒、メモリ制限は1024 MiBである。正の XX、非負の桁、正の先頭桁、d≤bd\leq b がそれぞれ候補の制限と復号の証明に必要である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Two Kinds of Base の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 素因数分解と約数構造

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 素因数・約数分解

    補助タグ: 貪欲法と交換論

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 素因数分解と約数構造

    • 整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。

    先に読む単元:

    この解説で扱わないこと:

    • 床関数や整数根の値が一定となる区間への分割。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題