独力で解けると楽しい。

solution

桁DP。半分全列挙。$O(\sqrt{M})$。

整数$n$が$9$っぽい$\phi(n)$とは、$\Sigma_i n_i \equiv n \pmod K$のちょうどそのとき。ただし$n_i$は$n$の$10$進数展開の下から$i$桁目($0$-based)の数字。 $n = \Sigma_i n_i \cdot 10^i$であるので、$\phi(n) \iff \Sigma_i n_i \cdot (10^i - 1) \equiv 0 \pmod K$と変形できる。 よって、各桁に重み$(10^i - 1) \bmod K$が乗っているときに、重みが$0$になるような桁の取り方の総数を求める問題として理解できる。

ここで、半分全列挙が使える。上位の桁と下位の桁でそれぞれ可能な重みの総和とその数を数え、対応を取る。 桁の選び方は基本的に独立であるので基本的に可能だが、$n \le M$であるという制限は考慮する必要がある。 この制約により実装が多少面倒になるが、それだけである。

implementation

#include <iostream>
#include <vector>
#include <unordered_map>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= (m); --(i))
typedef long long ll;
using namespace std;
bool is_nine_like(ll n, ll k) {
    ll x = n % k;
    ll y = 0; for (; n; n /= 10) y = (y + n % 10) % k;
    return x == y;
}
unordered_map<ll,ll> update(unordered_map<ll,ll> const & xs, ll e, ll k, int ten) {
    unordered_map<ll,ll> nxs;
    for (auto it : xs) {
        ll x, cnt; tie(x, cnt) = it;
        repeat (d,ten) {
            nxs[(x + d * e) % k] += cnt;
        }
    }
    return nxs;
}
ll product(unordered_map<ll,ll> const & xs, unordered_map<ll,ll> const & ys, ll acc, ll k) {
    ll cnt = 0;
    for (auto it : xs) {
        ll x, xcnt; tie(x, xcnt) = it;
        ll y = - (acc + x); y = (y % k + k) % k;
        if (ys.count(y)) {
            ll ycnt = ys.at(y);
            cnt += xcnt * ycnt;
        }
    }
    return cnt;
}
int main() {
    // input
    ll k; string s; cin >> k >> s;
    ll m = stoll(s);
    // prepare
    vector<ll> e; // e_i = 10^i
    for (ll it = 1; it <= m; it *= 10) e.push_back(it % k - 1);
    int r = e.size();
    int l = r/2;
    // enumerate
    vector<unordered_map<ll,ll> > xss(l+1); // lower
    xss[0][0] = 1;
    repeat (i,l) xss[i+1] = update(xss[i], e[i], k, 10);
    vector<unordered_map<ll,ll> > yss(r-l+1); // upper
    yss[0][0] = 1;
    repeat (i,r-l) yss[i+1] = update(yss[i], e[l+i], k, 10);
    // count
    ll ans = 0;
    ll acc = 0;
    repeat_from_reverse (i,l,r) {
        unordered_map<ll,ll> zs = update(yss[i-l], e[i], k, s[r-i-1]-'0');
        ans += product(xss.back(), zs, acc, k);
        acc = (acc + (s[r-i-1]-'0') * e[i]) % k;
    }
    repeat_reverse (i,l) {
        unordered_map<ll,ll> zs = update(xss[i], e[i], k, s[r-i-1]-'0');
        ans += zs[((- acc) % k + k) % k];
        acc = (acc + (s[r-i-1]-'0') * e[i]) % k;
    }
    // adjust
    ans -= 1; // for 0
    if (is_nine_like(m, k)) ans += 1; // for m itself
    // output
    cout << ans << endl;
    return 0;
}