概要

連続する \(3\) つの整数 \(x-1, x, x+1\) の桁和が、すべて同じ余り \(R\) になるような \(x\) の個数を数える問題です。

結論として、\(K \neq 1\) のとき条件を満たす \(x\) は存在せず、\(K=1\) のときはすべての \(2 \leq x \leq N-1\) が条件を満たします。

考察

整数 \(n\) から \(n+1\) に増えるとき、桁和がどう変化するかを考えます。

例えば、

• \(123 \to 124\) のように繰り上がりがない場合、桁和は \(1\) 増える
• \(129 \to 130\) のように繰り上がりがある場合、桁和は大きく減ることもある

ここで重要なのは、連続する \(3\) 数 \(x-1, x, x+1\) を考えたとき、次のどちらかが必ず成り立つことです。

• \(x\) の一の位が \(9\) でないなら、\(x \to x+1\) で繰り上がりが起きない
  よって $\( \mathrm{digitsum}(x+1) = \mathrm{digitsum}(x) + 1 \)$

• \(x\) の一の位が \(9\) なら、\(x-1\) の一の位は \(8\) なので、\(x-1 \to x\) で繰り上がりが起きない
  よって $\( \mathrm{digitsum}(x) = \mathrm{digitsum}(x-1) + 1 \)$

つまり、\(x-1 \to x\) または \(x \to x+1\) のどちらか一方では、必ず桁和がちょうど \(1\) 増えます。

条件では、\(x-1, x, x+1\) の桁和を \(K\) で割った余りがすべて同じ \(R\) である必要があります。

しかし、桁和が \(1\) 増える箇所があるなら、その前後の余りが同じになるためには

\[ 1 \equiv 0 \pmod K \]

である必要があります。

これは \(K=1\) のときしか成り立ちません。

したがって、

• \(K \neq 1\) のとき、答えは必ず \(0\)
• \(K=1\) のとき、すべての整数の桁和は \(1\) で割ると余り \(0\) なので、すべての \(x\) が条件を満たす

となります。

\(K=1\) の場合、制約より \(R=0\) です。

このとき条件を満たす \(x\) は

\[ 2 \leq x \leq N-1 \]

を満たすすべての整数なので、個数は

\[ N-2 \]

です。

ただし、\(N\) は非常に大きく、整数として扱えない可能性があるため、文字列として読み込み、\(10^9+7\) で割った余りを計算します。

アルゴリズム

1. 入力として文字列 \(N\)、整数 \(K\) を受け取る
2. \(K \neq 1\) なら、答えは \(0\)
3. \(K=1\) なら、答えは \(N-2\)
4. \(N\) は巨大なので、文字列を左から見ながら $\( v \leftarrow (10v + \text{次の桁}) \bmod (10^9+7) \)\( として \)N \bmod (10^9+7)$ を計算する
5. 最後に $\( (v - 2) \bmod (10^9+7) \)$ を出力する

計算量

• 時間計算量: \(O(|N|)\)
• 空間計算量: \(O(1)\)

実装のポイント

\(N\) の桁数は最大で \(5 \times 10^6\) なので、通常の整数型に変換せず、文字列またはバイト列として扱います。

Python では入力を sys.stdin.buffer.read() でまとめて読み込むと高速です。

また、コード中では N をバイト列として扱っているため、各桁 c は文字ではなく ASCII コードです。数字として使うには

c - 48

とします。ここで 48 は文字 '0' の ASCII コードです。

ソースコード

import sys

MOD = 10**9 + 7

data = sys.stdin.buffer.read().split()
N = data[0]
K = int(data[1])

if K != 1:
    print(0)
else:
    v = 0
    for c in N:
        v = (v * 10 + (c - 48)) % MOD
    print((v - 2) % MOD)

---

この解説は gpt-5.5-high によって生成されました。