桁DP. 先頭の桁の 0を無視しないといけないので， leading zero を保持する． 無視するというのは，積に使わないということ．
実装
Leading zero さえ持っておけば，あとは桁DP のテンプレ通り．
注意
- まだ \(N\) 未満が確定していないかつ ne > cu の場合は無効なので continue.
- if(nz) のときは，まだ leading zero が継続しているから，積の計算を保留しているので np = p.
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
map<ll,ll> dp[2][2];
map<ll,ll> old[2][2];
int main() {
string s; cin >> s;
ll k ; cin >> k;
ll inf = k+1;
dp[0][1][1] = 1;
rep(i,s.length()) {
rep(l,2) rep(z,2) old[l][z] = map<ll,ll>(); // remark: init, reset.
swap(dp, old);
rep(l,2) rep(z,2) for(auto [p,cnt]:old[l][z]){
ll cu = s[i]-'0';
rep(ne,10){
if(l == 0 && ne > cu) continue;
ll nl = l || (ne < cu);
ll nz = z && (ne == 0);
ll np = p;
if(!nz){
if(p*ne > k) np = inf;
else np *= ne;
}
dp[nl][nz][np] += cnt;
}
}
}
ll ans = 0;
rep(l,2) for(auto [p,cnt]: dp[l][0]) if(p <= k) ans += cnt;
cout << ans << endl;
return 0;
}
