fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. vector<int> digit;  
  12.  
  13. vector<int> getDigit(ll N) {
  14. 	vector<int> ans;  
  15. 	for (; N > 0; N /= 10) ans.push_back(N % 10);  
  16. 	return ans; 
  17. }
  18.  
  19. map<ll, ll> memo[19][2][2]; 
  20.  
  21. // leading = true tức đang là chữ số 0 đứng đầu, false tức là chữ số có nghĩa
  22. ll dp(int idx, bool leading, bool smaller, ll prod, ll K) {
  23. 	if (idx == -1) return (!leading && prod <= K);  
  24.  
  25. 	ll& ans = memo[idx][leading][smaller][prod];
  26. 	if (ans != 0) return ans; 
  27.  
  28. 	ans = 0; 
  29. 	int max_digit = (smaller) ? 9 : digit[idx]; 
  30.  
  31. 	for (int i = 0; i <= max_digit; i++) {
  32. 		bool new_leading = leading & (i == 0);
  33. 		ll new_prod = (new_leading) ? prod : prod * i;   
  34. 		ans += dp(idx - 1, new_leading, smaller | (i < digit[idx]), new_prod, K);  
  35. 	}	
  36.  
  37. 	return ans; 
  38. }
  39.  
  40. ll solve(ll N, ll K) {
  41. 	digit = getDigit(N);  
  42. 	return dp(digit.size() - 1, 1, 0, 1, K); 
  43. }
  44.  
  45. int main() {
  46. 	ios::sync_with_stdio(false); 
  47. 	cin.tie(nullptr); 	
  48. 	ll N, K; 
  49. 	cin >> N >> K; 
  50.  
  51. 	ll ans = solve(N, K); 
  52. 	cout << ans << '\n'; 
  53. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
13 2
stdout
copy 
5
https://ideone.com/E3SnyC
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!