AtCoder Beginner Contest 322 G問題メモ

AtCoder Beginner Contest 322

G - Two Kinds of Base

• $N,X$ が与えられる
• 同じ数字の並び $S=(S_1,S_2,...)$ を2つの異なる進数 $a,b$ で解釈することを考える
  • $(1,0,1,1,0)$ を2進数で解釈したら22、3進数で解釈したら93となる
• それぞれを10進数に変換したときの差がちょうど $X$ になるような $(S,a,b)$ の組の個数を求めよ
• ただし、以下を全て満たすものとする
  • $a,b \le N$
  • $0 \le S_i \lt \min(10,a,b)$
  • $1 \le S_1$
• $1 \le N \le 10^9$
• $1 \le X \le 2 \times 10^5$

指数を含む計算式の結果は、文字通り指数的に増えていくので、実は探索する範囲は広くない。適切に範囲を絞って全探索できる。

以下、表記の簡単さのため、$S$ の長さを $k+1$ として、添字を $(S_k,S_{k-1},...,S_0)$ とする。
$a$ 進数と解釈して10進数になおす操作を $f(S,a)$ とすると、$f(S,a)=a^kS_k+a^{k-1}S_{k-1}+...+S_0$ となる。

• $f(S,a)-f(S,b)=(a-b)S_1=X$

$S_0$ は何でもよい。$\min(10,a,b)$ だけの自由度がある。

$S_1$ を $1～9$ まで全探索する。

• $S_1$ が $X$ を割り切れないとダメ
  • 割り切れる場合、商を $d$ として、$d=a-b$ となる
• $N \ge a=b+d \gt b \gt S_1$ を満たすような $a,b$ に対し、それぞれ $\min(10,b)$ の答えがある

$S_1$ と $N$ に挟まれた制約から、条件を満たす $a,b$ の個数が計算できる。

こちらも $S_0$ は何でもよい。$(S_k,...,S_1,a,b)$ の組毎に、$\min(10,b)$ だけの自由度がある。

具体的に $k=3$ などとすると、以下のようになる。

• $f(S,a)-f(S,b)=(a^3-b^3)S_3+(a^2-b^2)S_2+(a-b)S_1=X$

$k→b→a$ の順に探索する。（別にこの通りでなくてもいいが、ここではこれで進める）

$k$ があんまり大きくなったらどんなに $a,b$ を小さくしても $X$ を超えてしまう。
$(a,b)$ の下限は $(3,2)$ なので、$k=12$ で $527345$ となり $X$ の上限を超えるので、探索範囲は多くない。

なので、まずは $k$ を探索する。

次に $b$ を最小の2から順に増やして探索する。
ここでも、$(b+1)^k-b^k \gt X$ になったら、もうこれ以上増やしても適切な組は見つからないので打ち切れる。

次に $a$ の範囲を考えるときに重要な要素として、以下の制約がある。

• $a^k-b^k,a^{k-1}-b^{k-1},...,a-b$ は全て、$a-b$ を因数に持つ
• つまり、$a-b$ は $X$ を割り切れないといけない

また、以下の事実がある（①）。

• $a^k-b^k \gt (b-1)(a^{k-1}-b^{k-1}+...+a-b)$

証明

①の式が表すのはつまり、$S$ を上位桁から決めていくときに、「$S_k$ をあと1増やしても $X$ を超えない」状況だったら、そこで増やさないと、$k-1$ 以降の桁を最大まで上げても $X$ に足りなくなるということ。

（例）(a,b)=(7,3), k=4, X=5000

a^k - b^k = 7^4 - 3^4 = 2320  →  5000/2320 = 2.155... なので、S4 は最大 2 にできる

このとき、S4 = 1 などにしてしまうと、S3,S2,S1 を全て最大(b-1 = 2)にしても、

(a^3-b^3)*2 + (a^2-b^2)*2 + (a-b)*2 = 720 < 2320

なので、2320減らした分を補えない。（他のa,b,k,Xでも必ずこうなる）
よって、S4 は最大の 2 にする必要がある。

$a,b,k$ が決まったら、上位桁 $t=k,k-1,...,1$ から $a^t-b^t$ が取れる最大限まで貪欲に取るしかないことになる。
特に、最高次数 $S_k$ は $\left\lfloor \dfrac{X}{a^k-b^k} \right\rfloor$ となる。

また $S_k$ は $1 \le S_k \lt \min(10,b)$ の範囲にないといけないことを考えると、（切り捨てとか些細な誤差は無視して）変形して

• $\sqrt[k]{\dfrac{X}{\min(10,b)}+b^k} \lt a \le \sqrt[k]{X+b^k}$

この範囲となる。各 $a$ に対し実際にテストする。

• $a-b$ が $X$ を割り切るか?
• 割り切る場合、貪欲に上位桁から決めていったら各桁 $S_i$ が $\min(10,b)$ に収まるか?

上手くいったら、$S_0$ の自由度 $\min(10,b)$ だけ答えに加算する。

Python3