fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define MP make_pair
  7. #define F first
  8. #define S second
  9. #define pi pair<int,int> 
  10. #define sz(s) ((int)s.size())
  11. #define rep(i,a,b) for (int i = a; i <= (int)b; ++i)
  12.  
  13. int dp[19][100][1<<11][2][2], n;
  14. string a, b;
  15. int mod;
  16.  
  17. int go(int id, int m, int mask, bool f, bool f3) {
  18.   if (id == a.size()) {
  19.     // cout << mask << '\n';
  20.     return !m && !(mask & (mask - 1));
  21.   }
  22.  
  23.   if (~dp[id][m][mask][f][f3]) return dp[id][m][mask][f][f3];
  24.  
  25.   int l = 0, r = 9;
  26.  
  27.   if (f3 == 0 && f == 0) {
  28.     l = a[id] - '0', r = b[id] - '0';
  29.   }
  30.   if (f3 && !f) {
  31.     l = a[id] - '0';
  32.   }
  33.   if (!f3 && f) {
  34.     r = b[id] - '0';
  35.   }
  36.   int dig = a[id] - '0', ans = 0;     
  37.   int c = m * 10;
  38.   while (c >= mod) c-=mod;
  39.   if (mask) l = max(l, 1LL);
  40.   for (int i = l; i <= r; ++i) {
  41.     int mask2 = mask;
  42.     if (i) {
  43.       for (int j = i; j < 10; j +=i) {
  44.         if (mask2 >> j & 1) mask2 ^= 1 << j;
  45.       }
  46.     }
  47.     if (i) mask2 |= 1 << i;
  48.     int pro = max(1LL, i);
  49.     int md = c + i;
  50.     while (md >= mod) md -= mod;
  51.     ans = max(ans, pro*go(id + 1, md, mask2, f | (a[id] - '0' < i), f3 | (i < b[id]-'0')));
  52.   }
  53.   return dp[id][m][mask][f][f3] = ans;
  54. }
  55.  
  56. string fin;
  57.  
  58. void construct(int id, int m, int mask, bool f, bool f3) {
  59.   if (id == a.size()) {   
  60.     return;
  61.   }
  62.   int ans = dp[id][m][mask][f][f3];
  63.   int l = 0, r = 9; 
  64.   if (f3 == 0 && f == 0) {
  65.     l = a[id] - '0', r = b[id] - '0';
  66.   }
  67.   if (f3 && !f) {
  68.     l = a[id] - '0';
  69.   }
  70.   if (!f3 && f) {
  71.     r = b[id] - '0';
  72.   }
  73.   int c = m * 10;
  74.   while (c >= mod) c-=mod;
  75.   if (mask) l = max(l, 1LL);
  76.  
  77.   for (int i = l; i <= r; ++i) {
  78.     int mask2 = mask;
  79.     if (i) {
  80.       for (int j = i; j < 10; j +=i) {
  81.         if (mask2 >> j & 1) mask2 ^= 1 << j;
  82.       }
  83.     }
  84.     if (i) mask2 |= 1 << i;
  85.     int pro = max(1LL, i);
  86.     int md = c + i;
  87.     while (md >= mod) md -= mod;
  88.     if (ans == pro*go(id + 1, md, mask2, f | (a[id] - '0' < i), f3 | (i < b[id]-'0'))) {
  89.       fin += i + '0';
  90.       construct(id + 1, md, mask2, f | (a[id] - '0' < i), f3 | (i < b[id]-'0'));
  91.       break;
  92.     }
  93.   }
  94.   return;
  95. }
  96.  
  97.  
  98. signed main() {
  99.   ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  100.   int t = 1, k, num; cin >> t;
  101.   while (t--) {    
  102.     cin >> num >> b >> k;
  103.     mod = k;    
  104.     fin.clear();
  105.     a = to_string(num-1);
  106.     while (a.size() != b.size())
  107.       a = '0' + a;
  108.     memset(dp, -1, sizeof dp);
  109.     int ans = go(0,0,0,0,0);
  110.     construct(0,0,0,0,0);
  111.     bool f = false;
  112.     if (ans) {
  113.       cout << ans << ' ';
  114.       for (int i = 0; i < fin.size(); ++i) {
  115.         f |= fin[i] > '0';
  116.         if (f) cout << fin[i];
  117.       }
  118.       cout << '\n';
  119.     }
  120.     else cout << -1 << '\n';
  121.   }
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.   return 0;
  130. }
Time limit exceeded #stdin #stdout 5s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZyA3gv
language:
C++14 (gcc 8.3)
created:
4 years 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!