概要

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

考察

隣り合う数の桁和の関係

まず、ある数 \(m\) から \(m+1\) になったとき、桁和がどう変化するかを考えます。

• \(m\) の末尾が \(9\) でない（末尾の \(9\) の個数が \(0\)）なら、桁上がりが起こらず桁和は \(+1\) されます。
• \(m\) の末尾に \(9\) が \(t\) 個連続している場合、それらの \(9\) がすべて \(0\) になり、その上の桁が \(+1\) されます。よって桁和は \(-9t + 1\) 変化します。

まとめると、\(m\) の末尾の \(9\) の個数を \(t\) とすると、

\[\mathrm{digitsum}(m+1) - \mathrm{digitsum}(m) = 1 - 9t\]

となります。

3 つの桁和が等しい条件

\(x-1, x, x+1\) の桁和がすべて \(K\) で割った余りが等しい、ということは、隣り合う差が \(K\) の倍数であることと同じです。つまり：

\[\mathrm{digitsum}(x) - \mathrm{digitsum}(x-1) \equiv 0 \pmod K\]

\[\mathrm{digitsum}(x+1) - \mathrm{digitsum}(x) \equiv 0 \pmod K\]

ここで、\(x-1\) の末尾の \(9\) の個数を \(t_1\)、\(x\) の末尾の \(9\) の個数を \(t_2\) とすると、上の差の公式より条件は次のようになります：

\[1 - 9 t_1 \equiv 0 \pmod K, \qquad 1 - 9 t_2 \equiv 0 \pmod K\]

重要な観察：\(t_1\) と \(t_2\) は同時に正にならない

\(x-1\) の末尾が \(9\)（つまり \(t_1 \geq 1\)）の場合を考えます。すると \(x = (x-1)+1\) の末尾は \(0\) になるので、\(x\) の末尾は \(9\) ではなく \(t_2 = 0\) です。

逆に \(x\) の末尾が \(9\)（\(t_2 \geq 1\)）なら、\(x-1\) の末尾は \(8\) なので \(t_1 = 0\) です。

したがって、\(t_1\) と \(t_2\) の少なくとも一方は必ず \(0\) です。

\(K \geq 2\) では解が存在しない

少なくとも一方、たとえば \(t_2 = 0\) だとすると、その条件は

\[1 - 9 \cdot 0 = 1 \equiv 0 \pmod K\]

となります。これは \(K\) が \(1\) を割り切ること、すなわち \(K = 1\) を意味します。\(K \geq 2\) では \(1 \equiv 0 \pmod K\) は成り立たないので、条件を満たす \(x\) は一つも存在しません。

（例：\(K=3\) のとき、\(9t\) は常に \(3\) の倍数なので \(1 - 9t \equiv 1 \pmod 3 \neq 0\)。よって連続する桁和の差が \(3\) の倍数になることはありません。）

\(K = 1\) の場合

\(K = 1\) のときは制約より \(R = 0\) で、どんな数の桁和も \(1\) で割った余りは \(0\) です。よって \(2 \leq x \leq N-1\) を満たすすべての \(x\) が条件を満たし、その個数は \(N - 2\) です。

アルゴリズム

以上から、場合分けするだけで答えが求まります。

• \(K = 1\) のとき：答えは \((N - 2) \bmod (10^9+7)\)
• \(K \geq 2\) のとき：答えは \(0\)

ただし \(N\) は最大 \(5 \times 10^6\) 桁の巨大な数なので、通常の整数型には収まりません。そこで \(N\) を文字列として読み込み、ホーナー法で先頭の桁から

\[r \leftarrow (r \times 10 + d) \bmod (10^9+7)\]

を繰り返して \(N \bmod (10^9+7)\) を計算し、最後に \(2\) を引いて（負にならないよう \(\mathrm{MOD}\) を足して）出力します。

計算量

• 時間計算量: \(O(|N|)\)（\(|N|\) は \(N\) の桁数。各桁を一度ずつ処理するだけ）
• 空間計算量: \(O(|N|)\)（入力文字列の保持分）

実装のポイント

• \(N\) が巨大なため、long long などに直接読み込めません。文字列として受け取り、\(\bmod\) を取りながら数値化します。

• 減算で負の値にならないよう、\((r - 2 + \mathrm{MOD}) \bmod \mathrm{MOD}\) のように \(\mathrm{MOD}\) を足してから余りを取ります。

• \(K \geq 2\) なら入力の \(N\) を数値化する必要すらなく、即座に \(0\) を出力できます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    long long K, R;
    cin >> N >> K >> R;

    const long long MOD = 1000000007;

    if(K == 1){
        // 全ての x (2 <= x <= N-1) が条件を満たす => 個数 N-2
        long long r = 0;
        for(char c : N){
            r = (r * 10 + (c - '0')) % MOD;
        }
        r = (r - 2 % MOD + MOD) % MOD;
        cout << r << "\n";
    } else {
        cout << 0 << "\n";
    }
    return 0;
}

---

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