AtCoder Beginner Contest 322 G問題メモ

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$ となる。

$k=1$ のとき

$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$ の個数が計算できる。

$k \ge 2$ のとき

こちらも $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

n, x = map(int, input().split())
ans = 0
MOD = 998244353

# k=1 のとき
# S=[s1, s2]
# s2はなんでもよい（0<=s2<min(10,a,b)）
# s1は、(a-b)s1=x
# よって、a>b>s1 な関係を満たすものにつき、s2の自由度分の答えがある
for s1 in range(1, 10):
    d, m = divmod(x, s1)
    if m > 0:
        continue
    for b in range(s1 + 1, 10):
        a = b + d
        if n < a:
            break
        ans += b
    a = 10 + d
    if n >= a:
        ans += (n - a + 1) * 10
    ans %= MOD


# k>=2 のとき
def check(a, b, k, x):
    if x % (a - b) > 0:
        return False
    max_s = min(b, 10)
    for t in range(k, 0, -1):
        s, x = divmod(x, a ** t - b ** t)
        if s >= max_s:
            return False
    return True


for k in range(2, 100000):
    # 一番小さい (a,b)=(3,2) でもxを超えたら終わり
    if 3 ** k - 2 ** k > x:
        break
    for b in range(2, n + 1):
        bk = b ** k
        # (b+1,b) でxを超えたら終わり
        if (b + 1) ** k - bk > x:
            break
        # (a**k - b**k)*max_s > x でないといけない
        max_s = min(10, b)
        min_a = max(b + 1, int(pow(x / max_s + bk, 1 / k)))
        for a in range(min_a, n + 1):
            if a ** k - bk > x:
                break
            if (a ** k - bk) * max_s <= x:
                continue
            if check(a, b, k, x):
                # 末尾要素の自由度分
                ans += max_s
        ans %= MOD

print(ans)

目次

AtCoder Beginner Contest 322 G問題メモ

G - Two Kinds of Base

問題

解法

$k=1$ のとき

$k \ge 2$ のとき