概要

連続する3つの整数 \(x-1, x, x+1\) それぞれの桁和を \(K\) で割った余りがすべて \(R\) になるような \(x\) の個数を求める問題です。

考察

まず、連続する整数の桁和の変化に注目します。整数 \(n\) の桁和を \(D(n)\) とします。 \(n\) に 1 を足すとき、桁和はどのように変化するでしょうか。 \(n\) の1の位が 9 でない場合、繰り上がりは発生せず、1の位が 1 増えるだけなので、\(D(n+1) = D(n) + 1\) となります。 一方、\(n\) の1の位が 9 の場合、繰り上がりが発生します。1の位は 9 から 0 に変わり（-9）、さらに上の桁が 1 増えるため（+1）、変化量は \(-8\) となります（9が連続する場合は \(-9k + 1\)）。

この性質を踏まえて、\(D(x-1) \equiv D(x) \equiv D(x+1) \pmod K\) を満たす \(x\) を探します。 \(x\) の1の位を \(d\) としたとき、以下の場合分けが考えられます。

1. \(d\) が \(1\) 以上 \(8\) 以下のとき \(x-1\) から \(x\) への変化、および \(x\) から \(x+1\) への変化で繰り上がり・繰り下がりは起きません。 したがって、\(D(x) - D(x-1) = 1\) および \(D(x+1) - D(x) = 1\) となります。 これらが \(K\) の倍数になるためには \(K = 1\) である必要があります。

2. \(d = 9\) のとき \(x\) から \(x+1\) への変化では繰り上がりが発生しますが、\(x-1\) から \(x\) への変化では1の位が 8 から 9 になるため繰り上がりは発生しません。 よって \(D(x) - D(x-1) = 1\) となり、これが \(K\) の倍数になるためには \(K = 1\) である必要があります。

3. \(d = 0\) のとき \(x-1\) から \(x\) への変化では繰り下がりが発生しますが、\(x\) から \(x+1\) への変化では1の位が 0 から 1 になるため繰り上がりは発生しません。 よって \(D(x+1) - D(x) = 1\) となり、これが \(K\) の倍数になるためには \(K = 1\) である必要があります。

いずれの場合も、\(K \geq 2\) のときは隣り合う桁和の差が \(\pm 1\) になる箇所が必ず存在し、それらが \(\pmod K\) で等しくなることはあり得ません。したがって、\(K \geq 2\) のとき条件を満たす \(x\) は存在しません。

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

アルゴリズム

1. 入力を受け取り、\(K\) が \(1\) でない場合は 0 を出力して終了します。
2. \(K = 1\) の場合、\(N - 2 \pmod{10^9+7}\) を計算します。
3. \(N\) は非常に大きな整数（最大 \(5 \times 10^6\) 桁）として文字列で与えられるため、1文字ずつ読み込みながら \(10^9+7\) で割った余りを計算します。
4. 計算した余りから \(2\) を引き、負にならないように \(10^9+7\) を足してから再度 \(10^9+7\) で割った余りを出力します。

計算量

• 時間計算量: \(O(L)\) （\(L\) は \(N\) の桁数）
• 空間計算量: \(O(L)\) （入力文字列の保存に必要）

実装のポイント

• \(N\) が巨大であるため、\(N\) を数値型に直接変換することはできません。文字列として処理し、1桁ずつmodを取っていく必要があります。

• \(N \bmod (10^9+7)\) を求めたあと、\(2\) を引く計算では結果が負になる可能性があるため、(n_mod - 2 + MOD) % MOD のように調整します。

  ソースコード

#include <iostream>
#include <string>

using namespace std;

const long long MOD = 1000000007;

int main() {
    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) {
        cout << 0 << "\n";
        return 0;
    }
    
    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;
}

この解説は or-glm5.2-high によって生成されました。