fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vl;
  9. typedef vector<pii> vii;
  10. typedef vector<pll> vll;
  11. #define all(x) (x).begin(),(x).end()
  12. #define pb push_back
  13. #define ff first
  14. #define ss second
  15. #define mp make_pair
  16.  
  17. int n, kand = 1;
  18. string A, B;
  19. mt19937 rng;
  20. vl dp, nast;
  21. vi pierw, odw, aktyw, nxt;
  22. int iter = 0;
  23.  
  24. bool cmp(int a, int b){
  25.     return a > b;
  26. }
  27.  
  28. ll mulmod(ll a, ll b, ll mod){
  29.     a %= mod; b %= mod;
  30.     return (a * b) % mod;
  31. }
  32.  
  33. ll powmod(ll a, ll b, ll mod){
  34.     ll r = 1;
  35.     while(b){
  36.         if(b & 1) r = mulmod(r, a, mod);
  37.         a = mulmod(a, a, mod);
  38.         b >>= 1;
  39.     }
  40.     return r;
  41. }
  42.  
  43. ll ext(ll a, ll b, ll& x, ll& y){
  44.     if(b == 0){
  45.         x = 1; y = 0;
  46.         return a;
  47.     }
  48.     ll x1, y1, g = ext(b, a % b, x1, y1);
  49.     x = y1; y = x1 - (a / b) * y1;
  50.     return g;
  51. }
  52.  
  53. ll inv(ll a, ll b){
  54.     ll x, y; ext(a, b, x, y);
  55.     x %= b; if(x < 0) x += b;
  56.     return x;
  57. }
  58.  
  59. ll rhopom(ll x, ll m, ll c){
  60.     return (mulmod(x, x, m) + c) % m;
  61. }
  62.  
  63. bool czy_pierwsza(int x){
  64.     if(x < 2) return false;
  65.     for(int p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}){
  66.         if(x % p == 0) return x == p;
  67.     }
  68.  
  69.     int d = x - 1, s = 0;
  70.     while(!(d & 1)){
  71.         d >>= 1; s++;
  72.     }
  73.     for(int a : {2, 7, 61}){
  74.         if(a % x == 0) continue;
  75.         ll z = powmod(a, d, x);
  76.         if(z == 1 || z == x - 1) continue;
  77.         bool czy = true;
  78.         for(int b = 1; b < s; b++){
  79.             z = mulmod(z, z, x);
  80.             if(z == x - 1){
  81.                 czy = false; break;
  82.             }
  83.         }
  84.         if(czy) return false;
  85.     }
  86.     return true;
  87. }
  88.  
  89. ll pollardRho(int m){
  90.     if(m % 2 == 0) return 2;
  91.     if(m % 3 == 0) return 3;
  92.     for(;;){
  93.         ll c = (ll)(rng() % (m - 1)) + 1;
  94.         ll x = (ll)(rng() % (m - 2)) + 2;
  95.         ll y = x, d = 1;
  96.         for(int it = 0; d == 1 && it < 100000; it++){
  97.             x = rhopom(x, m, c);
  98.             y = rhopom(rhopom(y, m, c), m, c);
  99.             d = __gcd(abs(x - y), ll(m));
  100.         }
  101.         if(d > 1 && d < m) return d;
  102.     }
  103. }
  104.  
  105. void faktoryzuj(int x, vi& f){
  106.     if(x == 1) return;
  107.     for(int p : pierw){
  108.         if(p * p > x) break;
  109.         while(x % p == 0){
  110.             f.pb(p); x /= p;
  111.         }
  112.         if(x == 1) return;
  113.     }
  114.     if(x == 1) return;
  115.     if(czy_pierwsza(x)){
  116.         f.pb(x); return;
  117.     }
  118.     ll d = pollardRho(x);
  119.     faktoryzuj(d, f);
  120.     faktoryzuj(x / d, f);
  121. }
  122.  
  123. void dzielniki(int x, vi& dziel){
  124.     vi f;
  125.     faktoryzuj(x, f);
  126.     sort(all(f));
  127.     dziel.clear(); dziel.pb(1);
  128.     int m = f.size();
  129.     for(int i = 0; i < m; i++){
  130.         int j = i;
  131.         while(j < m && f[i] == f[j]) j++;
  132.         int last = dziel.size(), akt = 1;
  133.         for(int w = i; w < j; w++){
  134.             akt *= f[i];
  135.             for(int k = 0; k < last; k++){
  136.                 dziel.pb(akt * dziel[k]);
  137.             }
  138.         }
  139.         i = j - 1;
  140.     }
  141. }
  142.  
  143. struct info{
  144.     string s;
  145.     int mn, mx;
  146.     vi poza;
  147.     int pocz, dl, suf;
  148.     ll W, M;
  149.     bool czy;
  150. };
  151.  
  152. int skrajne(string& a, int b){
  153.     int val = 0;
  154.     for(char c : a){
  155.         int x = b;
  156.         if(c != '?') x = int(c - '0');
  157.         val *= 10; val += x;
  158.     }
  159.     return val;
  160. }
  161.  
  162. int ile_zap(string& a){
  163.     int x = 0;
  164.     for(char c : a) if(c == '?') x++;
  165.     return x;
  166. }
  167.  
  168. bool czy_pasuje(string& a, int d){
  169.     if(d <= 0) return false;
  170.     for(int i = n - 1; i >= 0; i--){
  171.         int r = d % 10; d /= 10;
  172.         if(a[i] != '?' && int(a[i] - '0') != r) return false;
  173.     }
  174.     return d == 0;
  175. }
  176.  
  177. info prep(string& a){
  178.     int mn = skrajne(a, 0), mx = skrajne(a, 9);
  179.     vii przedzialy;
  180.     for(int i = 0; i < n; i++){
  181.         if(a[i] != '?') continue;
  182.         int j = i;
  183.         while(j < n && a[j] == '?') j++;
  184.         przedzialy.pb(mp(i, j - i));
  185.         i = j;
  186.     }
  187.  
  188.     int pocz = -1, dl = 0;
  189.     for(pii& kand : przedzialy){
  190.         if(kand.ss > dl){
  191.             pocz = kand.ff; dl = kand.ss;
  192.         }
  193.     }
  194.     vi pos;
  195.     ll M = 1, W = 1;
  196.     int suf = n - (pocz + dl);
  197.     if(dl){
  198.         for(int i = 0; i < pocz; i++) if(a[i] == '?') pos.pb(i);
  199.         for(int i = pocz + dl; i < n; i++) if(a[i] == '?') pos.pb(i);
  200.         for(int i = 0; i < suf; i++) W *= 10;
  201.         for(int i = 0; i < dl; i++) M *= 10;
  202.     }
  203.     return {a, mn, mx, pos, pocz, dl, suf, W, M, 1 - przedzialy.empty()};
  204. }
  205.  
  206. bool tozsame(){
  207.     for(int i = 0; i < n; i++)
  208.         if(A[i] != '?' && B[i] != '?' && A[i] != B[i])
  209.             return false;
  210.     return true;
  211. }
  212.  
  213. int wsp_max(){
  214.     int val = 0;
  215.     for(int i = 0; i < n; i++){
  216.         char pom;
  217.         int x;
  218.         if(A[i] != '?') pom = A[i];
  219.         else pom = B[i];
  220.         if(pom == '?') x = 9;
  221.         else x = int(pom - '0');
  222.         val *= 10; val += x;
  223.     }
  224.     return val;
  225. }
  226.  
  227. void prep_pierwsze(){
  228.     const int N = 1000;
  229.     vi f(N + 1, 0);
  230.     for(int i = 2; i <= N; i++){
  231.         if(!f[i]){
  232.             for(int j = i * i; j <= N; j += i) f[j] = 1;
  233.         }
  234.     }
  235.     for(int i = 2; i <= N; i++) if(!f[i]) pierw.pb(i);
  236. }
  237.  
  238. bool spr_row_diof(ll a, ll b, ll d, ll lim){
  239.     ll g = __gcd(b, d);
  240.     if(a % g != 0) return false;
  241.  
  242.     ll nd = d / g;
  243.  
  244.     if(nd < lim) return true;
  245.     if(nd == lim) return a > 0;
  246.  
  247.     ll pom = (nd - (a / g) % nd) % nd;
  248.     ll z = mulmod(pom, inv((b / g) % nd, nd), nd);
  249.  
  250.     return z < lim && (a > 0 || z > 0);
  251. }
  252.  
  253. bool czy_dziala_d_pom(string& s, int pos, info& a, int d){
  254.     if(pos == a.poza.size()){
  255.         ll x = 0;
  256.         for(char c : s){
  257.             x *= 10;
  258.             x += c - '0';
  259.         }
  260.         return spr_row_diof(x, a.W, d, a.M);
  261.     }
  262.  
  263.     int i = a.poza[pos];
  264.  
  265.     for(int z = 0; z <= 9; z++){
  266.         s[i] = char('0' + z);
  267.  
  268.         if(czy_dziala_d_pom(s, pos + 1, a, d)){
  269.             s[i] = '?';
  270.             return true;
  271.         }
  272.     }
  273.  
  274.     s[i] = '?';
  275.     return false;
  276. }
  277.  
  278. bool czy_dziala_d(int d, info& a){
  279.     int l = max(1, (a.mn + d - 1) / d);
  280.     int r = a.mx / d;
  281.  
  282.     if(r - l <= 20000){
  283.         for(int i = l; i <= r; i++){
  284.             if(czy_pasuje(a.s, d * i))
  285.                 return true;
  286.         }
  287.         return false;
  288.     }
  289.  
  290.     string t = a.s;
  291.     for(int i = a.pocz; i < a.pocz + a.dl; i++) t[i] = '0';
  292.  
  293.     return czy_dziala_d_pom(t, 0, a, d);
  294. }
  295.  
  296. void solver1_pom(string& s, info& b, int pos, ll val, vl& p10, vl& mxs, unordered_map<int, bool>& pam){
  297.  
  298.     if(val * p10[n - pos] + mxs[pos] <= kand) return;
  299.  
  300.     if(pos == n){
  301.         int x = val;
  302.  
  303.         if(x == 0) return;
  304.  
  305.         vi dziel;
  306.         dzielniki(x, dziel);
  307.         sort(all(dziel), cmp);
  308.  
  309.         for(int d : dziel){
  310.             if(d <= kand) break;
  311.             auto it = pam.find(d);
  312.             bool ok;
  313.             if(it != pam.end()) ok = it->ss;
  314.             else ok = pam[d] = czy_dziala_d(d, b);
  315.  
  316.             if(ok){
  317.                 kand = d;
  318.                 break;
  319.             }
  320.         }
  321.         return;
  322.     }
  323.  
  324.     if(s[pos] != '?'){
  325.         solver1_pom(s, b, pos + 1, val * 10 + s[pos] - '0', p10, mxs, pam);
  326.         return;
  327.     }
  328.  
  329.     for(int z = 9; z >= 0; z--){
  330.         ll nv = val * 10 + z;
  331.         if(nv * p10[n - pos - 1] + mxs[pos + 1] <= kand) break;
  332.         solver1_pom(s, b, pos + 1, nv, p10, mxs, pam);
  333.     }
  334. }
  335.  
  336. void solver1(string& s, info& b){
  337.     unordered_map<int, bool> pam;
  338.  
  339.     vl p10(n + 1, 1), mxs(n + 1, 0);
  340.  
  341.     for(int i = 1; i <= n; i++) p10[i] = p10[i - 1] * 10;
  342.     for(int i = n - 1; i >= 0; i--){
  343.         int x = int(s[i] - '0');
  344.         if(s[i] == '?') x = 9;
  345.         mxs[i] = x * p10[n - i - 1] + mxs[i + 1];
  346.     }
  347.  
  348.     solver1_pom(s, b, 0, 0, p10, mxs, pam);
  349. }
  350.  
  351. int solver2_pom(int p, int q, info& a, info& b){
  352.     ll lim = min(a.mx / p, b.mx / q);
  353.     ll dol = max(1LL, max(1ll * (a.mn + p - 1) / p, 1ll * (b.mn + q - 1) / q));
  354.  
  355.     if(lim <= kand || dol > lim) return 0;
  356.  
  357.     int roz = p * q;
  358.     if(dp.size() < roz){
  359.         dp.resize(roz);
  360.         nast.resize(roz);
  361.         odw.resize(roz, 0);
  362.     }
  363.     aktyw.clear();
  364.     nxt.clear();
  365.  
  366.     aktyw.pb(0);
  367.     dp[0] = 0;
  368.  
  369.     ll pot = 1;
  370.  
  371.     for(int i = n - 1; i >= 0; i--){
  372.         nxt.clear();
  373.  
  374.         if(iter == INT_MAX){
  375.             fill(all(odw), 0);
  376.             iter = 0;
  377.         }
  378.         iter++;
  379.  
  380.         for(int j : aktyw){
  381.             int ca = j / q, cb = j % q;
  382.             ll val = dp[j];
  383.  
  384.             if(val > lim) continue;
  385.  
  386.             ll first = val;
  387.             if(first < dol) first += (dol - first + pot - 1) / pot * pot;
  388.             if(first > lim) continue;
  389.  
  390.             ll last = val + (lim - val) / pot * pot;
  391.             if(last <= kand) continue;
  392.  
  393.             for(int z = 0; z <= 9; z++){
  394.                 int x = p * z + ca, y = q * z + cb, da = x % 10, db = y % 10;
  395.  
  396.                 if(a.s[i] != '?' && a.s[i] - '0' != da) continue;
  397.                 if(b.s[i] != '?' && b.s[i] - '0' != db) continue;
  398.  
  399.                 int na = x / 10, nb = y / 10, l = na * q + nb;
  400.                 ll nv = val + z * pot;
  401.                 if(odw[l] != iter){
  402.                     odw[l] = iter;
  403.                     nast[l] = nv;
  404.                     nxt.pb(l);
  405.                 }else nast[l] = max(nast[l], nv);
  406.             }
  407.         }
  408.  
  409.         dp.swap(nast);
  410.         aktyw.swap(nxt);
  411.  
  412.         if(aktyw.empty()) return 0;
  413.  
  414.         pot *= 10;
  415.     }
  416.  
  417.     if(odw[0] != iter) return 0;
  418.     return dp[0];
  419. }
  420.  
  421.  
  422. void solver2(bool& czy, info& a, info& b){
  423.     const int K = 1200;
  424.     int t = max(a.mx, b.mx);
  425.     czy = false;
  426.  
  427.     aktyw.reserve(2 * K + 5);
  428.     nxt.reserve(2 * K + 5);
  429.  
  430.     for(int k = 1; k <= K; k++){
  431.         if(t / k <= kand){
  432.             czy = true;
  433.             return;
  434.         }
  435.  
  436.         for(int p = 1; p <= k; p++){
  437.             int q = k;
  438.             if(min(a.mx / p, b.mx / q) <= kand) break;
  439.             if(__gcd(p, q) != 1) continue;
  440.             kand = max(kand, solver2_pom(p, q, a, b));
  441.             if(t / k <= kand){
  442.                 czy = true;
  443.                 return;
  444.             }
  445.         }
  446.  
  447.         for(int q = 1; q < k; q++){
  448.             int p = k;
  449.             if(min(a.mx / p, b.mx / q) <= kand) break;
  450.             if(__gcd(p, q) != 1) continue;
  451.             kand = max(kand, solver2_pom(p, q, a, b));
  452.             if(t / k <= kand){
  453.                 czy = true;
  454.                 return;
  455.             }
  456.         }
  457.  
  458.         if(t / (k + 1) <= kand){
  459.             czy = true;
  460.             return;
  461.         }
  462.     }
  463. }
  464.  
  465. int main(){
  466.     ios_base::sync_with_stdio(0);
  467.     cin.tie(0);
  468.  
  469.     rng.seed(67);
  470.     cin >> n >> A >> B;
  471.  
  472.     info ia = prep(A), ib = prep(B);
  473.  
  474.     if(tozsame()){
  475.         kand = wsp_max();
  476.         if(kand == min(ia.mx, ib.mx) || 2 * kand >= max(ia.mx, ib.mx)){
  477.             cout << kand << "\n";
  478.             return 0;
  479.         }
  480.     }
  481.  
  482.     int qa = ile_zap(A), qb = ile_zap(B);
  483.  
  484.     if(min(qa, qb) <= 5){
  485.         prep_pierwsze();
  486.         if(qa <= qb) solver1(A, ib);
  487.         else solver1(B, ia);
  488.  
  489.         cout << kand << "\n";
  490.         return 0;
  491.     }
  492.  
  493.     bool czy;
  494.     solver2(czy, ia, ib);
  495.  
  496.     if(!czy){
  497.         prep_pierwsze();
  498.         if(qa <= qb) solver1(A, ib);
  499.         else solver1(B, ia);
  500.     }
  501.  
  502.     cout << kand << "\n";
  503.     return 0;
  504. }
  505.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/v6P9AB
language:
C++ (gcc 8.3)
created:
20 hours 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!