概要

この問題は、連続する \(3\) つの整数の桁和（各桁の数字の和）を \(K\) で割った余りがすべて等しくなるような、 \(2 \leq x \leq N - 1\) の範囲にある整数 \(x\) の個数を求める問題です。

一見すると、非常に大きな数 \(N\) に対して桁DP（桁数に関する動的計画法）などを用いる複雑な問題に見えますが、連続する整数の桁和の性質に注目すると、数学的に非常にシンプルなルールに帰着できます。

---

考察

1. 隣り合う整数の桁和の差に注目する

整数 \(n\) と、それに \(1\) を足した \(n+1\) の桁和の関係を考えてみましょう。

• \(n\) の一の位が \(9\) ではないとき \(n\) から \(n+1\) になるとき、一の位が \(1\) 増えるだけなので、桁和はちょうど \(1\) 増えます。 $\(\mathrm{digitsum}(n+1) - \mathrm{digitsum}(n) = 1\)\( *例: \)123 \to 124\(（桁和は \)6 \to 7\(、差は \)1$）*

• \(n\) の一の位が \(9\) のとき 一の位が \(0\) に繰り上がり、さらに上の桁にも繰り上がりが発生するため、桁和は減少します。 例: \(129 \to 130\)（桁和は \(12 \to 4\)、差は \(-8\)）

2. 連続する 3 つの整数 \(x-1, x, x+1\) で考える

問題の条件は、連続する \(3\) つの数の桁和を \(K\) で割った余りがすべて等しいことです。 これは、隣り合う数の桁和の差が \(K\) の倍数 になっていることと同値です。すなわち、以下の \(2\) つが同時に成り立つ必要があります。 1. \(\mathrm{digitsum}(x) - \mathrm{digitsum}(x-1) \equiv 0 \pmod K\) 2. \(\mathrm{digitsum}(x+1) - \mathrm{digitsum}(x) \equiv 0 \pmod K\)

ここで、 \(x-1\) の一の位が何であるかによって場合分けをします。

• \(x-1\) の一の位が \(9\) ではない場合 1 の性質より、 \(\mathrm{digitsum}(x) - \mathrm{digitsum}(x-1) = 1\) となります。 これが \(K\) の倍数であるためには、 \(1 \equiv 0 \pmod K\)、すなわち \(K = 1\) である必要があります。

• \(x-1\) の一の位が \(9\) である場合 このとき、 \(x\) の一の位は必ず \(0\) になります。 \(x\) の一の位は \(9\) ではないため、今度は \(x\) と \(x+1\) の関係において、 \(\mathrm{digitsum}(x+1) - \mathrm{digitsum}(x) = 1\) となります。 これが \(K\) の倍数であるためには、やはり \(K = 1\) である必要があります。

結論

どのような整数 \(x\) を選んでも、 \(x-1 \to x\) または \(x \to x+1\) の少なくとも一方では繰り上がりが発生しません。 繰り上がりが発生しない箇所の桁和の差は必ず \(1\) になるため、余りが等しくなる（差が \(K\) の倍数になる）ためには \(K = 1\) であることが絶対条件となります。

• \(K > 1\) のとき：条件を満たす \(x\) は存在しません。答えは常に 0 です。
• \(K = 1\) のとき：任意の整数の桁和を \(1\) で割った余りは常に \(0\)（\(R=0\)）です。したがって、 \(2 \leq x \leq N - 1\) の範囲にあるすべての整数が条件を満たします。答えは \(N - 2\) 個となります。

---

アルゴリズム

1. \(K\) の値を確認します。
2. \(K > 1\) の場合
   • 答えは 0 です。
3. \(K = 1\) の場合
   • 答えは \(N - 2 \pmod{10^9 + 7}\) です。
   • \(N\) は最大で \(5 \times 10^6\) 桁の非常に大きな数であるため、文字列として受け取り、上から順に \(10^9 + 7\) で割った余りを計算します（大きな数の剰余演算）。
   • 求めた余りから \(2\) を引きます。このとき、値が負にならないように (N_mod - 2 + MOD) % MOD として計算します。

---

計算量

\(N\) の桁数を \(L\) とします（\(L \le 5 \times 10^6\)）。

• 時間計算量: \(O(L)\) \(N\) の各桁を上から順に \(1\) 回ずつ走査して剰余を計算するため、桁数に比例した時間で処理が完了します。
• 空間計算量: \(O(L)\) 入力された巨大な整数 \(N\) を文字列としてメモリに保持するために必要なメモリ量です。

---

実装のポイント

• 巨大な数の余りの求め方 文字列 N の各文字 c について、 N_mod = (N_mod * 10 + (c - '0')) % MOD と更新していくことで、オーバーフローを防ぎながら \(N \bmod (10^9+7)\) を求めることができます。

• 負の数の剰余への配慮 \(N \bmod (10^9+7)\) が \(0\) または \(1\) の場合、 \(2\) を引くと値が負になってしまいます。C++などの言語では負の数に対する % 演算が負の値を返すことがあるため、あらかじめ MOD を足してから % MOD を取ることで安全に計算できます。

  ソースコード

#include <iostream>
#include <string>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string N;
    long long K, R;
    if (!(cin >> N >> K >> R)) return 0;

    if (K > 1) {
        // It is mathematically impossible to have 3 consecutive identical digit sums modulo K for K > 1.
        cout << 0 << "\n";
    } else {
        // For K = 1, R is always 0, and all x in [2, N - 1] satisfy the condition.
        // The answer is (N - 2) mod (10^9 + 7).
        long long MOD = 1000000007;
        long long N_mod = 0;
        for (char c : N) {
            N_mod = (N_mod * 10 + (c - '0')) % MOD;
        }
        long long ans = (N_mod - 2 + MOD) % MOD;
        cout << ans << "\n";
    }

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。