fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;    
  3.  
  4. /*/---------------------------Defines-----------------------------------------/*/
  5.  
  6. #pragma GCC optimize("Ofast") 
  7. #define int long long
  8. #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
  9. #define pb push_back 
  10. #define eb emplace_back
  11. #define fn for(int i =0 ;i <n;i++)  
  12. #define fn1 for( int i =1;i<=n; i++)
  13. #define fm for(int j =0 ;j <m;j++)
  14. #define fm1 for(int j =1;j<=m;j++)
  15. #define fi first
  16. #define se second
  17. #define endl '\n'
  18. #define PI  3.14159265358979323846
  19. #define MOD 1000000007
  20. #define all(a) a.begin(),a.end()
  21. #define rall(a) a.rbegin(),a.rend()
  22. const int N = 2e6+5;    
  23. const int INF = 1e18L;
  24. // for all eight directions
  25. int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  26. int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  27. // for all 4 directions
  28. //int dx[4]={-1,1,0,0};
  29. //int dy[4]={0,0,-1,1};
  30. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  31. /*/-----------------------------Debug begins----------------------------------/*/
  32. vector<string> split(const string& s, char c) {
  33.   vector<string> v; stringstream ss(s); string x;
  34.   while (getline(ss, x, c)) v.emplace_back(x); return move(v);
  35. }
  36. template<typename T, typename... Args>
  37. inline string arrStr(T arr, int n) {
  38.   stringstream s; s << "[";
  39.   for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
  40.   if(n>0)
  41.   s << arr[n - 1] ;
  42.   s<< "]";
  43.   return s.str();
  44. }
  45. #define trace(args...) {__trace_begin(__LINE__); __trace(split(#args, ',').begin(), args);}
  46. inline void __trace_begin(int line) { cerr << "#" << line << ": "; }
  47. template<typename T> inline void __trace_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
  48. template<typename T> inline void __trace_out_var(T* val) { cerr << arrStr(val, 10); }
  49. template<typename T> inline void __trace_out_var(T val) { cerr << val; }
  50. inline void __trace(vector<string>::iterator it) { cerr << endl; }
  51.  
  52. template<typename T, typename... Args>
  53. inline void __trace(vector<string>::iterator it, T a, Args... args) {
  54.   cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
  55.   __trace_out_var(a);
  56.   cerr << "; ";
  57.   __trace(++it, args...);
  58. }
  59. /*/-----------------------------Code begins----------------------------------/*/
  60. int ar[N];
  61. map<pair<pair<int,int>,pair<bool,bool> >,int>dp;
  62. int n,k;
  63. vector<int>v;
  64. string no;
  65. int solve(int pos,int p,bool f,bool st){
  66.   if(pos == n){
  67.     return p<=k;
  68.   }
  69.   if(dp.find({{pos,p},{f,st}})!=dp.end())return dp[{{pos,p},{f,st}}];
  70.   int ans =0 ;
  71.   int lim = (f ==0 ?  v[pos] : 9);
  72.   for(int i=0;i<=lim;i++){
  73.     bool nf =f ;
  74.     int np = p;
  75.     np*=i;
  76.     if(f ==0 && i < lim)nf =1;
  77.     if(i ==0 && st ==0 ){
  78.       ans+=solve(pos+1,p,nf,0);
  79.     }else{
  80.       ans+=solve(pos+1,np,nf,1);
  81.     }
  82.   }
  83.   return dp[{{pos,p},{f,st}}] =ans;
  84. }
  85. signed main(){
  86.   IOS;
  87.   int T=1;
  88.   // cin >> T;
  89.   while(T--){
  90.     cin >> n >> k ;
  91.     while(n){
  92.       v.pb(n%10);
  93.       n/=10;
  94.     }
  95.     reverse(all(v));
  96.     n = v.size();
  97.     int ans = solve(0,1,0,0);
  98.     --ans;
  99.     cout << ans;
  100.   }
  101.   return 0;
  102. }
Success #stdin #stdout 0.24s 13216KB
comments (?)
stdin
copy 
1000000000000000000 1000000000
stdout
copy 
841103275147365677
https://ideone.com/UkEzTO
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!