この問題は、いわゆる桁 DP を使って解くことができます。

桁 DP とは、整数を（例えば十進表記の）文字列と捉え、一桁ずつ桁を追加することと対応する状態遷移を実装することで条件を満たす整数全体に対して DP を行う手法です。 特に、「\(N\) 以下の整数」を管理するために「すでに \(N\) 以下になることが確定しているか」のフラグを用いるものを指して桁 DP と呼ぶことも多いです。

この問題では、一般的な「\(N\) 以下の整数全体」に対して処理を行う桁 DP に加えて、「確定していない部分の桁積が何の倍数である必要があるか」などを持つことで高速に解くことができます。

実装例は以下のようになります。 以下の実装例ではメモ化再帰を使って桁 DP を行っています。

#include <iostream>
#include <map>
#include <algorithm>
#include <numeric>

int main() {
    using namespace std;
    string N;
    int M;
    cin >> N >> M;
    ranges::reverse(N); // 下の位を先頭にしておく

    // memo[digit, m, full] := 桁積が m の倍数である digit 桁の (full ? 整数の個数 : N の digit 桁目以降 以下の整数の個数) 
    map<tuple<int, int, bool>, long> memo;
    auto dp = [&N, &memo](this auto self, int digit, int m, bool full) -> long {
        if (memo.contains({digit, m, full})) {
            return memo[{digit, m, full}];
        }
        if (digit == -1) {
            return m == 1;
        }

        long ans = 0;
        if (full) { // 桁に制限がないとき
            for (int d = 1; d <= 9; ++d) { // 1 から 9 まで
                ans += self(digit - 1, m / gcd(m, d), true);
            }
        } else { // N の digit 桁以降以下なら
            int upper = N[digit] - '0';
            for (int d = 1; d <= upper; ++d) { // 1 から N の digit 桁目まで
                ans += self(digit - 1, m / gcd(m, d), d < upper);
            }
        }
        return memo[{digit, m, full}] = ans;
    };

    long ans = 0;
    for (int i = 0; i < size(N); ++i) {
        ans += dp(i, M, i + 1 < size(N)); // i+1 桁の整数ごとに求める
    }
    cout << ans << endl;
    return 0;
}