fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ull = unsigned long long;
  6.  
  7. int n;
  8. string A, B;
  9. vector<ll> pot10;
  10. vector<int> primes;
  11.  
  12. ll maxValue(const string& s) {
  13.     ll x = 0;
  14.     for (char c : s)
  15.         x = x * 10 + (c == '?' ? 9 : c - '0');
  16.     return x;
  17. }
  18.  
  19. ll parseNumber(const string& s) {
  20.     ll x = 0;
  21.     for (char c : s)
  22.         x = x * 10 + (c - '0');
  23.     return x;
  24. }
  25.  
  26. int countQuestions(const string& s) {
  27.     return count(s.begin(), s.end(), '?');
  28. }
  29.  
  30. bool matches(const string& pattern, ll x) {
  31.     if (x <= 0) return false;
  32.  
  33.     string s = to_string(x);
  34.     if ((int)s.size() > (int)pattern.size())
  35.         return false;
  36.  
  37.     s = string(pattern.size() - s.size(), '0') + s;
  38.  
  39.     for (int i = 0; i < (int)pattern.size(); ++i) {
  40.         if (pattern[i] != '?' && pattern[i] != s[i])
  41.             return false;
  42.     }
  43.  
  44.     return true;
  45. }
  46.  
  47. // Czy istnieje dodatnie uzupełnienie patternu
  48. // podzielne przez d? DP po resztach modulo d.
  49. bool hasMultipleDP(const string& pattern, int d) {
  50.     vector<array<unsigned char, 2>> cur(d), nxt(d);
  51.  
  52.     for (auto& x : cur) x = {0, 0};
  53.     cur[0][0] = 1;
  54.  
  55.     for (char c : pattern) {
  56.         for (auto& x : nxt) x = {0, 0};
  57.  
  58.         int lo = (c == '?' ? 0 : c - '0');
  59.         int hi = (c == '?' ? 9 : c - '0');
  60.  
  61.         for (int r = 0; r < d; ++r) {
  62.             for (int nz = 0; nz <= 1; ++nz) {
  63.                 if (!cur[r][nz]) continue;
  64.  
  65.                 for (int digit = lo; digit <= hi; ++digit) {
  66.                     int nr = (int)(((ll)r * 10 + digit) % d);
  67.                     int nnz = nz || digit != 0;
  68.                     nxt[nr][nnz] = 1;
  69.                 }
  70.             }
  71.         }
  72.  
  73.         cur.swap(nxt);
  74.     }
  75.  
  76.     return cur[0][1];
  77. }
  78.  
  79. ll extgcd(ll a, ll b, ll& x, ll& y) {
  80.     if (b == 0) {
  81.         x = 1;
  82.         y = 0;
  83.         return a;
  84.     }
  85.  
  86.     ll x1, y1;
  87.     ll g = extgcd(b, a % b, x1, y1);
  88.  
  89.     x = y1;
  90.     y = x1 - (a / b) * y1;
  91.  
  92.     return g;
  93. }
  94.  
  95. ll modInverse(ll a, ll mod) {
  96.     ll x, y;
  97.     extgcd(a, mod, x, y);
  98.  
  99.     x %= mod;
  100.     if (x < 0) x += mod;
  101.  
  102.     return x;
  103. }
  104.  
  105. // Czy pattern ma dodatnią wielokrotność d?
  106. // Jeżeli końcówka patternu zawiera ustalone cyfry,
  107. // wykorzystujemy kongruencję modulo 10^k.
  108. bool hasMultiple(const string& pattern, ll maxVal, ll d) {
  109.     if (d == 1) return maxVal >= 1;
  110.  
  111.     ll cnt = maxVal / d;
  112.  
  113.     int k = 0;
  114.     while (k < (int)pattern.size() &&
  115.            pattern[(int)pattern.size() - 1 - k] != '?') {
  116.         ++k;
  117.     }
  118.  
  119.     if (k > 0) {
  120.         ll mod10 = 1;
  121.         ll rem = 0;
  122.  
  123.         for (int i = (int)pattern.size() - k;
  124.              i < (int)pattern.size(); ++i) {
  125.             rem = rem * 10 + (pattern[i] - '0');
  126.             mod10 *= 10;
  127.         }
  128.  
  129.         ll g = __gcd(d, mod10);
  130.         if (rem % g != 0) return false;
  131.  
  132.         ll step = mod10 / g;
  133.         ll first;
  134.  
  135.         if (step == 1) {
  136.             first = 1;
  137.         } else {
  138.             ll dd = (d / g) % step;
  139.             ll rr = (rem / g) % step;
  140.  
  141.             first = (rr * modInverse(dd, step)) % step;
  142.             if (first == 0) first = step;
  143.         }
  144.  
  145.         for (ll t = first; t <= cnt; t += step) {
  146.             if (matches(pattern, d * t))
  147.                 return true;
  148.         }
  149.  
  150.         return false;
  151.     }
  152.  
  153.     // Bez ustalonej końcówki wybieramy tańszą metodę.
  154.     if (d <= 100000 && cnt > 90 * d)
  155.         return hasMultipleDP(pattern, (int)d);
  156.  
  157.     for (ll t = 1, x = d; t <= cnt; ++t, x += d) {
  158.         if (matches(pattern, x))
  159.             return true;
  160.     }
  161.  
  162.     return false;
  163. }
  164.  
  165. // Dzielniki x w kolejności malejącej.
  166. vector<ll> getDivisors(ll x) {
  167.     vector<pair<ll, int>> fac;
  168.     ll z = x;
  169.  
  170.     for (int p : primes) {
  171.         if (1LL * p * p > z) break;
  172.  
  173.         if (z % p == 0) {
  174.             int e = 0;
  175.             while (z % p == 0) {
  176.                 z /= p;
  177.                 ++e;
  178.             }
  179.             fac.push_back({p, e});
  180.         }
  181.     }
  182.  
  183.     if (z > 1)
  184.         fac.push_back({z, 1});
  185.  
  186.     vector<ll> divs{1};
  187.  
  188.     for (auto [p, e] : fac) {
  189.         size_t oldSize = divs.size();
  190.         ll mul = 1;
  191.  
  192.         for (int j = 1; j <= e; ++j) {
  193.             mul *= p;
  194.             for (size_t i = 0; i < oldSize; ++i)
  195.                 divs.push_back(divs[i] * mul);
  196.         }
  197.     }
  198.  
  199.     sort(divs.rbegin(), divs.rend());
  200.     return divs;
  201. }
  202.  
  203. // Stan DP dla mnożenia p*g i q*g.
  204. // ca, cb: przeniesienia obu mnożeń.
  205. // hist: ostatnie cyfry g potrzebne do kolejnych kolumn.
  206. struct State {
  207.     int ca, cb, hist;
  208.  
  209.     bool operator==(const State& o) const {
  210.         return ca == o.ca && cb == o.cb && hist == o.hist;
  211.     }
  212. };
  213.  
  214. struct StateHash {
  215.     static ull mix(ull x) {
  216.         x += 0x9e3779b97f4a7c15ULL;
  217.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
  218.         x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
  219.         return x ^ (x >> 31);
  220.     }
  221.  
  222.     size_t operator()(const State& s) const {
  223.         ull h = mix((unsigned)s.ca);
  224.         h ^= mix((unsigned)s.cb + 0x123456789ULL);
  225.         h ^= mix((unsigned)s.hist + 0x987654321ULL);
  226.         return (size_t)h;
  227.     }
  228. };
  229.  
  230. vector<int> digitsLE(int x) {
  231.     vector<int> d;
  232.  
  233.     while (x > 0) {
  234.         d.push_back(x % 10);
  235.         x /= 10;
  236.     }
  237.  
  238.     if (d.empty()) d.push_back(0);
  239.     return d;
  240. }
  241.  
  242. // Największe g takie, że p*g pasuje do A,
  243. // q*g pasuje do B. Wywołujemy dla __gcd(p,q)=1.
  244. ll solveRatio(int p, int q) {
  245.     vector<int> pd = digitsLE(p);
  246.     vector<int> qd = digitsLE(q);
  247.  
  248.     int t = max(pd.size(), qd.size());
  249.  
  250.     int base = 1;
  251.     for (int i = 0; i < t - 1; ++i)
  252.         base *= 10;
  253.  
  254.     vector<int> histPow(max(1, t), 1);
  255.     for (int i = 1; i < t; ++i)
  256.         histPow[i] = histPow[i - 1] * 10;
  257.  
  258.     // Przetwarzamy również pozycje nad cyframi wyniku,
  259.     // aby wymusić, że oba iloczyny mieszczą się w n cyfrach.
  260.     int L = n + t;
  261.  
  262.     unordered_map<State, ll, StateHash> cur, nxt;
  263.     cur.reserve(256);
  264.     nxt.reserve(256);
  265.     cur[{0, 0, 0}] = 0;
  266.  
  267.     ll answer = 0;
  268.  
  269.     for (int i = 0; i < L; ++i) {
  270.         nxt.clear();
  271.  
  272.         if (cur.size() < 2000000)
  273.             nxt.reserve(cur.size() * 2 + 16);
  274.  
  275.         int zhi = (i < n ? 9 : 0);
  276.  
  277.         for (const auto& [st, val] : cur) {
  278.             for (int z = 0; z <= zhi; ++z) {
  279.                 ll sa = st.ca;
  280.                 ll sb = st.cb;
  281.  
  282.                 // Cyfra pozycji i w iloczynie p*g.
  283.                 for (int j = 0; j < (int)pd.size(); ++j) {
  284.                     int k = i - j;
  285.                     if (k < 0) break;
  286.  
  287.                     int gd;
  288.                     if (k >= n) gd = 0;
  289.                     else if (j == 0) gd = z;
  290.                     else gd = (st.hist / histPow[j - 1]) % 10;
  291.  
  292.                     sa += (ll)pd[j] * gd;
  293.                 }
  294.  
  295.                 // Cyfra pozycji i w iloczynie q*g.
  296.                 for (int j = 0; j < (int)qd.size(); ++j) {
  297.                     int k = i - j;
  298.                     if (k < 0) break;
  299.  
  300.                     int gd;
  301.                     if (k >= n) gd = 0;
  302.                     else if (j == 0) gd = z;
  303.                     else gd = (st.hist / histPow[j - 1]) % 10;
  304.  
  305.                     sb += (ll)qd[j] * gd;
  306.                 }
  307.  
  308.                 int da = sa % 10;
  309.                 int db = sb % 10;
  310.  
  311.                 int ca2 = sa / 10;
  312.                 int cb2 = sb / 10;
  313.  
  314.                 bool okA =
  315.                     (i >= n ? da == 0 :
  316.                      (A[n - 1 - i] == '?' ||
  317.                       A[n - 1 - i] - '0' == da));
  318.  
  319.                 bool okB =
  320.                     (i >= n ? db == 0 :
  321.                      (B[n - 1 - i] == '?' ||
  322.                       B[n - 1 - i] - '0' == db));
  323.  
  324.                 if (!okA || !okB) continue;
  325.  
  326.                 if (i == L - 1 && (ca2 != 0 || cb2 != 0))
  327.                     continue;
  328.  
  329.                 int nh = (base == 1 ? 0 :
  330.                     (int)(((ll)st.hist * 10 + z) % base));
  331.  
  332.                 ll nv = val;
  333.                 if (i < n)
  334.                     nv += (ll)z * pot10[i];
  335.  
  336.                 if (i == L - 1) {
  337.                     answer = max(answer, nv);
  338.                 } else {
  339.                     State ns{ca2, cb2, nh};
  340.                     auto it = nxt.find(ns);
  341.  
  342.                     if (it == nxt.end())
  343.                         nxt.emplace(ns, nv);
  344.                     else
  345.                         it->second = max(it->second, nv);
  346.                 }
  347.             }
  348.         }
  349.  
  350.         cur.swap(nxt);
  351.  
  352.         if (cur.empty() && i < L - 1)
  353.             return 0;
  354.     }
  355.  
  356.     return answer;
  357. }
  358.  
  359. int main() {
  360.     ios::sync_with_stdio(false);
  361.     cin.tie(nullptr);
  362.  
  363.     cin >> n >> A >> B;
  364.  
  365.     // Sito liczb pierwszych do rozkładu liczb < 10^9.
  366.     vector<bool> isPrime(31624, true);
  367.     isPrime[0] = isPrime[1] = false;
  368.  
  369.     for (int i = 2; 1LL * i * i < (int)isPrime.size(); ++i) {
  370.         if (isPrime[i]) {
  371.             for (int j = i * i; j < (int)isPrime.size(); j += i)
  372.                 isPrime[j] = false;
  373.         }
  374.     }
  375.  
  376.     for (int i = 2; i < (int)isPrime.size(); ++i) {
  377.         if (isPrime[i]) primes.push_back(i);
  378.     }
  379.  
  380.     pot10.assign(n, 1);
  381.     for (int i = 1; i < n; ++i)
  382.         pot10[i] = pot10[i - 1] * 10;
  383.  
  384.     int qa = countQuestions(A);
  385.     int qb = countQuestions(B);
  386.  
  387.     ll maxA = maxValue(A);
  388.     ll maxB = maxValue(B);
  389.  
  390.     // Para maksymalnych uzupełnień już osiąga górną granicę.
  391.     ll initialBest = __gcd(maxA, maxB);
  392.     if (initialBest == min(maxA, maxB)) {
  393.         cout << initialBest << '\n';
  394.         return 0;
  395.     }
  396.  
  397.     // Jedna liczba jest całkowicie dowolna.
  398.     if (qa == n) {
  399.         cout << maxB << '\n';
  400.         return 0;
  401.     }
  402.  
  403.     if (qb == n) {
  404.         cout << maxA << '\n';
  405.         return 0;
  406.     }
  407.  
  408.     // Jeden napis jest ustaloną liczbą.
  409.     if (qa == 0 || qb == 0) {
  410.         ll x = (qa == 0 ? parseNumber(A) : parseNumber(B));
  411.         const string& pat = (qa == 0 ? B : A);
  412.         ll maxPat = (qa == 0 ? maxB : maxA);
  413.  
  414.         ll best = __gcd(x, maxPat);
  415.         auto divs = getDivisors(x);
  416.  
  417.         for (ll d : divs) {
  418.             if (d <= best) break;
  419.  
  420.             if (hasMultiple(pat, maxPat, d)) {
  421.                 best = d;
  422.                 break;
  423.             }
  424.         }
  425.  
  426.         cout << best << '\n';
  427.         return 0;
  428.     }
  429.  
  430.     // Oba napisy mają najwyżej 5 znaków zapytania.
  431.     // Zbieramy wszystkie dzielniki uzupełnień jednego z nich.
  432.     if (max(qa, qb) <= 5) {
  433.         const string& pat = (qa >= qb ? A : B);
  434.         const string& other = (qa >= qb ? B : A);
  435.  
  436.         vector<int> wildOther;
  437.         for (int i = 0; i < n; ++i) {
  438.             if (other[i] == '?') wildOther.push_back(i);
  439.         }
  440.  
  441.         string so = other;
  442.         vector<uint32_t> allDivisors;
  443.  
  444.         function<void(int)> build = [&](int pos) {
  445.             if (pos == (int)wildOther.size()) {
  446.                 ll y = parseNumber(so);
  447.                 if (y == 0) return;
  448.  
  449.                 auto divs = getDivisors(y);
  450.                 for (ll d : divs)
  451.                     allDivisors.push_back((uint32_t)d);
  452.  
  453.                 return;
  454.             }
  455.  
  456.             int idx = wildOther[pos];
  457.  
  458.             for (int digit = 0; digit <= 9; ++digit) {
  459.                 so[idx] = char('0' + digit);
  460.                 build(pos + 1);
  461.             }
  462.         };
  463.  
  464.         build(0);
  465.  
  466.         sort(allDivisors.begin(), allDivisors.end());
  467.         allDivisors.erase(
  468.             unique(allDivisors.begin(), allDivisors.end()),
  469.             allDivisors.end()
  470.         );
  471.  
  472.         vector<int> wildPat;
  473.         for (int i = 0; i < n; ++i) {
  474.             if (pat[i] == '?') wildPat.push_back(i);
  475.         }
  476.  
  477.         string sp = pat;
  478.         ll best = __gcd(maxA, maxB);
  479.  
  480.         function<void(int)> search = [&](int pos) {
  481.             if (maxValue(sp) <= best) return;
  482.  
  483.             if (pos == (int)wildPat.size()) {
  484.                 ll x = parseNumber(sp);
  485.                 if (x == 0) return;
  486.  
  487.                 auto divs = getDivisors(x);
  488.  
  489.                 for (ll d : divs) {
  490.                     if (d <= best) break;
  491.  
  492.                     if (binary_search(
  493.                             allDivisors.begin(),
  494.                             allDivisors.end(),
  495.                             (uint32_t)d)) {
  496.                         best = d;
  497.                         break;
  498.                     }
  499.                 }
  500.  
  501.                 return;
  502.             }
  503.  
  504.             int idx = wildPat[pos];
  505.  
  506.             for (int digit = 9; digit >= 0; --digit) {
  507.                 sp[idx] = char('0' + digit);
  508.                 search(pos + 1);
  509.             }
  510.  
  511.             sp[idx] = '?';
  512.         };
  513.  
  514.         search(0);
  515.  
  516.         cout << best << '\n';
  517.         return 0;
  518.     }
  519.  
  520.     // Jeden napis ma najwyżej 5 znaków zapytania,
  521.     // drugi ma ich więcej. Enumerujemy uzupełnienia
  522.     // mniej elastycznego napisu.
  523.     if (min(qa, qb) <= 5) {
  524.         const string& pat = (qa <= qb ? A : B);
  525.         const string& other = (qa <= qb ? B : A);
  526.         ll maxOther = (qa <= qb ? maxB : maxA);
  527.  
  528.         vector<int> vars;
  529.         for (int i = 0; i < n; ++i) {
  530.             if (pat[i] == '?') vars.push_back(i);
  531.         }
  532.  
  533.         string s = pat;
  534.         ll best = __gcd(maxA, maxB);
  535.  
  536.         unordered_map<ll, unsigned char> cache;
  537.         cache.reserve(100000);
  538.  
  539.         function<void(int)> dfs = [&](int pos) {
  540.             if (maxValue(s) <= best) return;
  541.  
  542.             if (pos == (int)vars.size()) {
  543.                 ll x = parseNumber(s);
  544.                 if (x == 0) return;
  545.  
  546.                 auto divs = getDivisors(x);
  547.  
  548.                 for (ll d : divs) {
  549.                     if (d <= best) break;
  550.  
  551.                     auto it = cache.find(d);
  552.                     bool ok;
  553.  
  554.                     if (it != cache.end()) {
  555.                         ok = it->second;
  556.                     } else {
  557.                         ok = hasMultiple(other, maxOther, d);
  558.                         cache.emplace(d, (unsigned char)ok);
  559.                     }
  560.  
  561.                     if (ok) {
  562.                         best = d;
  563.                         break;
  564.                     }
  565.                 }
  566.  
  567.                 return;
  568.             }
  569.  
  570.             int idx = vars[pos];
  571.  
  572.             for (int digit = 9; digit >= 0; --digit) {
  573.                 s[idx] = char('0' + digit);
  574.                 dfs(pos + 1);
  575.             }
  576.  
  577.             s[idx] = '?';
  578.         };
  579.  
  580.         dfs(0);
  581.  
  582.         cout << best << '\n';
  583.         return 0;
  584.     }
  585.  
  586.     // Pozostał trudny przypadek: oba napisy mają co najmniej
  587.     // 6 znaków zapytania.
  588.     ll best = __gcd(maxA, maxB);
  589.  
  590.     // Szybkie, poprawne uzupełnienia dające dolne ograniczenie.
  591.     for (int digit = 0; digit <= 9; ++digit) {
  592.         string a = A, b = B;
  593.  
  594.         for (char& c : a)
  595.             if (c == '?') c = char('0' + digit);
  596.  
  597.         for (char& c : b)
  598.             if (c == '?') c = char('0' + digit);
  599.  
  600.         ll x = parseNumber(a);
  601.         ll y = parseNumber(b);
  602.  
  603.         if (x && y)
  604.             best = max(best, __gcd(x, y));
  605.     }
  606.  
  607.     // Jeśli oba napisy dają się uzupełnić do tej samej liczby,
  608.     // sprawdzamy również największe wspólne uzupełnienie.
  609.     bool compatible = true;
  610.     string c = A;
  611.  
  612.     for (int i = 0; i < n; ++i) {
  613.         if (A[i] != '?' && B[i] != '?' && A[i] != B[i])
  614.             compatible = false;
  615.  
  616.         if (A[i] == '?' && B[i] != '?')
  617.             c[i] = B[i];
  618.         else if (A[i] != '?')
  619.             c[i] = A[i];
  620.         else
  621.             c[i] = '9';
  622.     }
  623.  
  624.     if (compatible) {
  625.         ll x = parseNumber(c);
  626.         best = max(best, x);
  627.     }
  628.  
  629.     if (best >= min(maxA, maxB)) {
  630.         cout << best << '\n';
  631.         return 0;
  632.     }
  633.  
  634.     // Każde rozwiązanie o NWD g > best ma postać:
  635.     // x = p*g, y = q*g, gdzie __gcd(p,q)=1.
  636.     // Wtedy p <= maxA/(best+1), q <= maxB/(best+1).
  637.     for (ll m = 1;; ++m) {
  638.         ll limP = maxA / (best + 1);
  639.         ll limQ = maxB / (best + 1);
  640.  
  641.         if (m > max(limP, limQ)) break;
  642.  
  643.         int upP = (int)min(m, limP);
  644.         int upQ = (int)min(m, limQ);
  645.  
  646.         for (int p = 1; p <= upP; ++p) {
  647.             for (int q = 1; q <= upQ; ++q) {
  648.                 if (max(p, q) != m) continue;
  649.                 if (__gcd(p, q) != 1) continue;
  650.  
  651.                 ll g = solveRatio(p, q);
  652.                 best = max(best, g);
  653.             }
  654.         }
  655.     }
  656.  
  657.     cout << best << '\n';
  658.     return 0;
  659. }
Success #stdin #stdout 2.17s 5324KB
comments (?)
stdin 
9
??????000
??????001
stdout 
999999
https://ideone.com/5P480o
language:
C++ (gcc 8.3)
created:
3 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!