AtCoder Regular Contest 052 D - 9
解法
K の値に応じて場合分けします。
K が小さい場合は, 桁dp で解けます。よくある dp[桁][あまりの差][smallFlag] ってやつです。
K が大きい場合は, 各桁の和がせいぜい 100 であることを利用します。すると, 解の候補は i*K+j (i*K+j <= M, 0 <= j <= 100) を調べれば良いだけなので十分時間内に間に合います。
const int S = 100000; int calc(ll x) { int ret = 0; while (x) { ret += x%10; x /= 10; } return ret; } // 桁, あまり, flag ll dp[20][S][2]; int p10[20]; int main() { cin.tie(0); ios::sync_with_stdio(false); ll K, M; cin >> K >> M; ll ans = 0; if (K >= S) { for (int i = 0; i*K <= M; i++) { for (int j = 0; j < 100 && i*K+j <= M; j++) { ll tmp = i*K+j; if (calc(tmp) == tmp%K) ans++; } } } else { p10[0] = 1; for (int i = 1; i < 20; i++) p10[i] = (p10[i-1]*10) % K; string s = to_string(M); int n = s.size(); dp[0][0][0] = 1; for (int keta = 0; keta < n; keta++) for (int q = 0; q < K; q++) for (int flag = 0; flag < 2; flag++) { if (!dp[keta][q][flag]) continue; for (int i = 0; i < 10; i++) { if (!flag && i > s[keta]-'0') continue; int nq = q; nq += (i*p10[n-1-keta])-i; nq %= K; if (nq < 0) nq += K; int nflag = flag; if (i < s[keta]-'0') nflag = 1; dp[keta+1][nq][nflag] += dp[keta][q][flag]; } } ans = dp[n][0][0]+dp[n][0][1]; } cout << ans-1 << endl; return 0; }