概要

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

重要なのは、\(K \neq 1\) のときそのような \(x\) は存在せず、\(K = 1\) のときはすべての \(x\) が条件を満たす、という点です。

考察

整数 \(n\) から \(n+1\) に進むときの桁和の変化を考えます。

例えば、

• \(123 \to 124\) のように、末尾が \(9\) でなければ桁和は \(1\) 増えます。
  • \(\mathrm{digitsum}(124) = \mathrm{digitsum}(123) + 1\)
• \(129 \to 130\) のように、末尾が \(9\) なら繰り上がりが発生します。
  • \(\mathrm{digitsum}(129) = 12\)
  • \(\mathrm{digitsum}(130) = 4\)

ここで、連続する \(3\) 数 \(x-1, x, x+1\) を考えます。

\(x-1\) が \(9\) で終わらない場合、繰り上がりは起きないので、

\[ \mathrm{digitsum}(x) = \mathrm{digitsum}(x-1) + 1 \]

です。

この \(2\) つの桁和を \(K\) で割った余りが等しいなら、

\[ 1 \equiv 0 \pmod K \]

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

一方、\(x-1\) が \(9\) で終わる場合、\(x\) は必ず \(0\) で終わります。

例：

• \(19 \to 20\)
• \(129 \to 130\)
• \(999 \to 1000\)

つまり、\(x\) は \(9\) で終わらないので、今度は \(x \to x+1\) で繰り上がりが起きません。

したがって、

\[ \mathrm{digitsum}(x+1) = \mathrm{digitsum}(x) + 1 \]

となります。

この場合も、\(2\) つの桁和の余りが等しいためには \(K=1\) が必要です。

よって、\(K \neq 1\) のとき、条件を満たす \(x\) は存在しません。

逆に \(K=1\) のとき、任意の整数の桁和を \(1\) で割った余りは必ず \(0\) です。

制約より \(R=0\) なので、すべての \(x\) が条件を満たします。

\(x\) の範囲は

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

なので、個数は

\[ N-2 \]

です。

ただし \(N\) は非常に大きく、通常の整数型には収まらない可能性があります。そのため、文字列として読み込み、\(N \bmod (10^9+7)\) を計算します。

アルゴリズム

1. \(N, K, R\) を入力する。
2. \(K \neq 1\) なら、答えは \(0\)。
3. \(K = 1\) なら、答えは \(N-2\)。
4. \(N\) は文字列で与えられるので、各桁を左から見て

\[ \text{nmod} = (\text{nmod} \times 10 + \text{digit}) \bmod (10^9+7) \]

として \(N \bmod (10^9+7)\) を求める。 5. 答えとして

\[ (N-2) \bmod (10^9+7) \]

を出力する。

計算量

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

ここで \(|N|\) は \(N\) の十進表記の長さです。

実装のポイント

\(N\) は最大で \(5 \times 10^6\) 桁あるため、整数型に変換してはいけません。

また、\(N-2\) を modulo で計算するとき、負の値を避けるために

\[ (\text{nmod} - 2 + MOD) \bmod MOD \]

のように計算します。

ソースコード

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

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

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

    const long long MOD = 1000000007LL;

    if (K != 1) {
        cout << 0 << '\n';
        return 0;
    }

    long long nmod = 0;
    for (char c : N) {
        nmod = (nmod * 10 + (c - '0')) % MOD;
    }

    cout << (nmod - 2 + MOD) % MOD << '\n';
    return 0;
}

---

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