fork download
copy 
  1. // وَمَا تَوْفِيقِي إِلَّا بِاللَّهِ عَلَيْهِ تَوَكَّلْتُ وَإِلَيْهِ أُنِيبُ
  2.  
  3. #include <bits/stdc++.h>
  4. #define T int t;cin>>t;while(t--)
  5. #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
  6. #define endl '\n'
  7. #define F first
  8. #define S second
  9. #define int long long
  10. using namespace std;
  11. int n,x,vis[10][2][10][19690][2],p10[11],p3[11],tc=0;
  12. pair<int,int> dp[10][2][10][19690][2];
  13. string s;
  14. int power(int a,int b) {
  15.     int r = 1;
  16.     while(b) {
  17.         if (b & 1) r = (r*a);
  18.         a = (a*a);
  19.         b = b >> 1;
  20.     }
  21.     return r;
  22. }
  23. int ask(int mask,int d) {
  24.     return (mask/p3[d-1]) % 3;
  25. }
  26. int add(int mask,int d) {
  27.     return mask + p3[d-1];
  28. }
  29. pair<int,int> dpwkeda(int i,bool tight,int last,int mask,bool start) {
  30.     if (i==s.size()) return {start,0};
  31.  
  32.     if (vis[i][tight][last][mask][start] == tc) return dp[i][tight][last][mask][start];
  33.  
  34.     int limit = tight ? s[i]-'0' : 9;
  35.     pair<int,int> ans = {0,0};
  36.     for (int j=0;j<=limit;j++) {
  37.         bool nxtTight = tight && limit == j;
  38.         if (j==0 && !start) {
  39.             pair<int,int> x = dpwkeda(i+1,nxtTight,last,mask,false);
  40.             int m = s.size()-i-1;
  41.             ans.F += x.F;
  42.             ans.S += (x.S + (x.F * (j * p10[m])));
  43.             continue;
  44.         }
  45.         if (j==0 && start) continue;
  46.         if (__gcd(j,last)!=1) continue;
  47.         if (ask(mask,j)==2) continue;
  48.         if (!start) {
  49.             pair<int,int> x = dpwkeda(i+1,nxtTight,j,add(mask,j),true);
  50.             int m = s.size()-i-1;
  51.             ans.F += x.F;
  52.             ans.S += (x.S + (x.F * (j * p10[m])));
  53.         }
  54.         else {
  55.             if (j==0) continue;
  56.             pair<int,int> k = dpwkeda(i+1,nxtTight,j,add(mask,j),1);
  57.             int m = s.size()-i-1;
  58.             ans.F += k.F;
  59.             ans.S += (k.S + (k.F * (j * p10[m])));
  60.         }
  61.     }
  62.     vis[i][tight][last][mask][start] = tc;
  63.     return dp[i][tight][last][mask][start] = ans;
  64. }
  65. pair<int,int> can(int mid) {
  66.     s = to_string(mid);
  67.     tc++;
  68.     return dpwkeda(0,true,1,0,0);
  69. }
  70. void Abady() {
  71.     cin >> n >> x;
  72.     for (int i=0;i<=9;i++) {
  73.         p10[i] = power(10,i);
  74.         p3[i] = power(3,i);
  75.     }
  76.     int l = 0 , r = x , ans = -1;
  77.     while (l <= r) {
  78.         int mid = (l+r)/2;
  79.         pair<int,int> f = can(mid);
  80.         if (f.F >= n) {
  81.             ans = f.S;
  82.             r = mid - 1;
  83.         }
  84.         else l = mid + 1;
  85.     }
  86.     cout << ans << endl;
  87. }
  88.  
  89. signed main() {
  90. #ifdef ABADY
  91.     freopen("input.txt", "r", stdin);
  92.     freopen("output.txt", "w", stdout);
  93. #endif
  94.     fast;
  95.     Abady();
  96. }
Success #stdin #stdout 0.04s 126820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gSLtSl
language:
C++14 (clang 8.0)
created:
5 days 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!