概要

連続する \(3\) つの番号 \(x-1, x, x+1\) の桁和がすべて \(K\) で割って \(R\) 余るような \(x\) の個数を求める問題です。実は答えは「\(K=1\) なら \(N-2\)、そうでなければ \(0\)」になります。

考察

連続する数の桁和の関係に注目する

ポイントは「連続する整数の桁和が、どのくらい変化するか」です。整数 \(x\) の桁和を \(s = \mathrm{digitsum}(x)\) とおき、\(x\) の一の位 \(d\) で場合分けします。

• \(1 \le d \le 8\) のとき（繰り上がり・繰り下がりが起きない）

  • \(\mathrm{digitsum}(x-1) = s-1\)
  • \(\mathrm{digitsum}(x+1) = s+1\)
  • 両隣の桁和が \(x\) とちょうど \(1\) だけ違います。

• \(d = 0\) のとき（\(x\) は末尾に \(0\) が並ぶ）

  • \(x+1\) は一の位が \(1\) になるだけなので \(\mathrm{digitsum}(x+1) = s+1\)。
  • \(x\) と \(x+1\) の桁和がちょうど \(1\) 違います。

• \(d = 9\) のとき（\(x\) は末尾に \(9\) が並ぶ）

  • \(x-1\) は一の位が \(8\) になるだけなので \(\mathrm{digitsum}(x-1) = s-1\)。
  • \(x\) と \(x-1\) の桁和がちょうど \(1\) 違います。

つまり どんな \(x\) についても、\(x-1\) か \(x+1\) の少なくとも一方は、\(x\) と桁和がちょうど \(1\) だけ異なります。

条件を満たすには \(K=1\) が必要

\(3\) つの桁和がすべて \(K\) で割って同じ余り \(R\) になるためには、桁和が \(1\) だけ違う \(2\) つの数が $\(s \equiv s+1 \pmod{K}\)\( を満たす必要があり、これは \)K \mid 1\(、すなわち \)K = 1$ のときしか成り立ちません。

したがって：

• \(K \neq 1\) のとき：条件を満たす \(x\) は存在しないので答えは \(0\)。
• \(K = 1\) のとき：すべての整数の桁和 \(\bmod\ 1\) は \(0\) であり、必ず \(R=0\) と一致します。よって \(2 \le x \le N-1\) を満たすすべての \(x\) が条件を満たし、その個数は \(N - 2\) 個です。

素朴な実装の問題点

\(K=1\) のときの答えは \(N-2\) ですが、\(N\) は最大 \(5 \times 10^6\) 桁という巨大な数で、文字列として与えられます。Python では多倍長整数を扱えるものの、\(N\) 全体を一度に int に変換すると変換コストが大きくなりがちです。最終的に \(10^9+7\) で割った余りだけが必要なので、余りを取りながら \(N\) を計算することで高速化します。

アルゴリズム

1. \(K \neq 1\) なら \(0\) を出力して終了。
2. \(K = 1\) なら \(N \bmod (10^9+7)\) を求め、そこから \(2\) を引いて出力する。

\(N \bmod p\) は Horner 法（左から \(1\) 桁ずつ取り込む方法）で計算できます： $\(\mathrm{acc} \leftarrow (\mathrm{acc} \times 10 + d) \bmod p\)$

ただし \(1\) 桁ずつだと反復回数が多くなるため、本コードでは \(18\) 桁ずつのチャンクにまとめて処理しています。\(18\) 桁の数は \(10^{18}\) 未満で安全に扱え、

\[\mathrm{acc} \leftarrow (\mathrm{acc} \times 10^{18} + (\text{18桁ブロックの値})) \bmod p\]

と更新します。最後に余った端数は、その桁数 \(r\) を使って \(\mathrm{acc} \times 10^{r} + (\text{端数})\) で処理します。

計算量

\(N\) の桁数を \(L\) とします。

• 時間計算量: \(O(L)\)（チャンクごとの int 変換と剰余演算の総和が桁数に比例）
• 空間計算量: \(O(L)\)（入力文字列の保持）

実装のポイント

• 早期判定：\(K \neq 1\) の場合は \(N\) を一切計算せずに \(0\) を出力でき、無駄な処理を省けます。

• チャンク処理：\(18\) 桁ずつまとめて int に変換することで、\(1\) 桁ずつ処理するより高速になります。10^{18} をあらかじめ \(\bmod p\) で計算した mult を使い回します。

• 負の剰余対策：(acc - 2) % MOD のように Python の % を使えば、結果が負になっても正しく \([0, MOD)\) の範囲に収まります（\(N \ge 3\) なので実際には負にはなりませんが、剰余を取った後の値から \(2\) を引くため念のため剰余演算で安全にしています）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = data[0]
    K = int(data[1])
    # R = int(data[2])  # K==1 のときは R==0 のみ
    MOD = 10**9 + 7
    if K != 1:
        sys.stdout.write("0\n")
        return
    # K == 1: 全ての x が条件を満たす。個数 = N - 2
    chunk = 18
    mult = pow(10, chunk, MOD)
    acc = 0
    n = len(N)
    # 完全なチャンクをまとめて処理
    i = 0
    # 先頭の端数を処理してアラインメントしてもよいが、左から順に処理する
    while i + chunk <= n:
        block = int(N[i:i+chunk])
        acc = (acc * mult + block) % MOD
        i += chunk
    if i < n:
        block = int(N[i:n])
        acc = (acc * pow(10, n - i, MOD) + block) % MOD
    ans = (acc - 2) % MOD
    sys.stdout.write(str(ans) + "\n")

main()

---

この解説は claude4.8opus-high によって生成されました。