この問題は桁に関する条件を満たす整数の個数を数え上げる問題です。こうした問題は 桁 DP と呼ばれる種類の動的計画法が効果的なことが多く、実際この問題も桁 DP を利用すれば高速に解くことが出来ます。(桁 DP に関する詳細な説明は他のホームページ等に譲ります。)

この問題は、はじめに桁和 \(s\) を決め打って考えるのがポイントです。つまり、\(s = 1, 2, \dots, 9 \times 14\) と固定した場合において問題を解いて、全ての \(s\) に対する答えを足し合わせたものが全体の答えになります。
\(s\) を決め打った時の問題を考えると、これは DP の状態を

• \(dp_{d, i, j, f}\) \(:=\) (上から \(d\) 桁目まで決めたとき、桁和が \(i\) で、 \(\text{mod }s\) が \(j\) で、\(f=0\) ならば \(N\) 未満、\(f=1\) ならば \(N\) と一致しているような整数の個数)

とおいて桁 DP を行うと、\(d + 1\) 桁目を \(t\) とした時に

\[dp[d + 1][i + t][(10 j + t) \bmod s][(大小関係に関する情報)] \text{ += } dp[d][i][j][f]\]

という渡す DP 型の遷移に基づいて答えを計算できます。(実装例も参考にしてください)

計算量は \(B = 10\) として全体で \(\mathrm{O}((B \log N)^4)\) です。(ここでの \(\log N\) は \(N\) の桁数の意味なので底は \(10\) で、\((B \log_{10} N)^4 \leq (140)^4 \simeq 3.8 \times 10^8\) となります。通常より数値が大きいですが、実行時間制限が \(10\) 秒と緩めに設定されているため、適切に実装できれば時間内に収まる程度に高速に動作します。)

• 実装例(C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); i++)

int main() {
  string N;
  cin >> N;
  long long ans = 0;
  for (int s = 1; s <= 9 * 14; s++) {
    vector dp(N.size() + 1, vector(s + 1, vector(s, vector(2, 0LL))));
    dp[0][0][0][1] = 1;
    rep(d, N.size()) rep(i, s + 1) rep(j, s) rep(f, 2) rep(t, 10) {
      if (i + t > s) continue;
      if (f and N[d] - '0' < t) continue;
      dp[d + 1][i + t][(j * 10 + t) % s][f and N[d] - '0' == t] += dp[d][i][j][f];
    }
    ans += dp[N.size()][s][0][0] + dp[N.size()][s][0][1];
  }
  cout << ans << endl;
}