API tools faq
paste
Advertisement
playerr17

Untitled

playerr17
Apr 27th, 2024
729
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.33 KB | None | 0 0
raw download clone embed print report
  1. //#include <cassert>
  2. //
  3. ///** Begin fast allocation */
  4. //const int MAX_MEM = 2e8 + 6e7;
  5. //int mpos = 0;
  6. //char mem[MAX_MEM];
  7. //inline void * operator new (size_t n) {
  8. //    assert((mpos += n) <= MAX_MEM);
  9. //    return (void *)(mem + mpos - n);
  10. //}
  11. //void operator delete (void *) noexcept { } // must have!
  12. //void operator delete (void *, size_t) noexcept { } // must have!
  13. ///** End fast allocation */
  14. #pragma GCC optimize("Ofast")
  15. //#pragma GCC optimize ("unroll-loops")
  16. //#pragma GCC optimize ("fast-math")
  17. #pragma GCC target("avx2")
  18. //#include <bits/stdc++.h>
  19. #include <iostream>
  20. #include <algorithm>
  21. #include <string>
  22. #include <cmath>
  23. #include <vector>
  24. #include <map>
  25. #include <set>
  26. #include <list>
  27. #include <ctime>
  28. #include <stack>
  29. #include <queue>
  30. #include <iomanip>
  31. #include <cstdlib>
  32. #include <unordered_map>
  33. #include <unordered_set>
  34. #include <cstddef>
  35. #include <deque>
  36. #include <cstdio>
  37. #include <fstream>
  38. #include <random>
  39. #include <climits>
  40. #include <cassert>
  41. #include <chrono>
  42. #include <complex>
  43.  
  44. using namespace std;
  45. #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
  46. #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
  47. #define pb push_back
  48. #define mp make_pair
  49. #define f first
  50. #define s second
  51. #define all(x) begin(x), end(x)
  52. #define sz(a) ((int)((a).size()))
  53. #define endl '\n'
  54. const int INF = 1e9 + 1;
  55. const long long MOD = 1'000'000'007;
  56. const long double EPS = 1e-6;
  57. typedef long long ll;
  58. typedef unsigned long long ull;
  59. typedef long double ld;
  60. std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
  61. struct hash_function {
  62.    size_t operator() (const pair<int, int>& p) const {
  63.        return p.first ^ p.second;
  64.    }
  65. };
  66.  
  67. double pi = atan2(0., -1.);
  68. const int LOG = 20;
  69. const int SZ = (1 << LOG);
  70.  
  71. int rev[SZ];
  72. complex <double> alpha[SZ];
  73.  
  74. void initFFT()
  75. {
  76.    for (int i = 1; i < SZ; i++)
  77.    {
  78.        int it = 0;
  79.        while (!(i & (1 << it) ) ) it++;
  80.        rev[i] = rev[i ^ (1 << it) ] ^ (1 << (LOG - it - 1) );
  81.    }
  82.    for (int i = 0; i < SZ; i++)
  83.    {
  84.        double x = pi * i / (double) SZ;
  85.        alpha[i] = complex <double> (cos(x), sin(x) );
  86.    }
  87. }
  88.  
  89. vector <complex <double> > FFT(vector <complex <double> > &st)
  90. {
  91.    int n = (int) st.size();
  92.    int k = 0;
  93.    while ( (1 << k) < n) k++;
  94.    if ( (1 << k) != n) throw;
  95.    vector <complex <double> > v, oth;
  96.    oth.resize(n);
  97.    v.resize(n);
  98.    for (int i = 0; i < n; i++)
  99.        v[rev[i] >> (LOG - k) ] = st[i];
  100.  
  101.    for (int it = LOG - k; it < LOG; it++)
  102.    {
  103.        int half = (n >> (LOG - it) );
  104.        for (int pos = 0; pos < n; pos += (half << 1) )
  105.        {
  106.            for (int i = 0; i < half; i++)
  107.            {
  108.                complex <double> a = v[pos + i];
  109.                complex <double> b = v[pos + half + i] * alpha[i << (LOG - k + LOG - it)];
  110.                oth[pos + i] = a + b;
  111.                oth[pos + half + i] = a - b;
  112.            }
  113.        }
  114.        v.swap(oth);
  115.    }
  116.  
  117.    return v;
  118. }
  119.  
  120. vector <complex <double> > FFT(const vector <int> &v, int n)
  121. {
  122.    vector <complex <double> > cv(n, 0.);
  123.    for (int i = 0; i < (int) v.size(); i++)
  124.        cv[i] = complex <double> (v[i] );
  125.  
  126.    return FFT(cv);
  127. }
  128.  
  129.  
  130. vector <int> mulFFT(const vector <int> &a, const vector <int> &b)
  131. {
  132.    int n = (int) a.size() + (int) b.size();
  133.    while (n & (n - 1) ) n++;
  134.  
  135.    vector <complex <double> > A = FFT(a, n);
  136.    vector <complex <double> > B = FFT(b, n);
  137.  
  138.    for (int i = 0; i < n; i++)
  139.        A[i] *= B[i];
  140.  
  141.    B = FFT(A);
  142.    reverse(B.begin() + 1, B.end() );
  143.    for (auto &it : B)
  144.        it /= n;
  145.  
  146. //  eprintf("1\n");
  147.    vector <int> ans;
  148.    ans.resize(n);
  149. //  eprintf("2\n");
  150. //  eprintf("%d\n", (int) ans.size() );
  151. //  eprintf("%d n = %d\n", (int) B.size(), n);
  152.    for (int i = 0; i < n; i++)
  153.        ans[i] = ((long long) (B[i].real() + 0.5));// % MOD;
  154. //  eprintf("3\n");
  155.  
  156.    for (int i = 0; i < n - 1; ++i) {
  157.        if (ans[i] >= 10) {
  158.            ans[i + 1] += ans[i] / 10;
  159.            ans[i] %= 10;
  160.        }
  161.    }
  162.  
  163.    return ans;
  164. }
  165.  
  166. vector<int> to_num(const string& s) {
  167.    vector<int> a;
  168.    for (auto i : s) {
  169.        a.push_back(i - '0');
  170.    }
  171.    reverse(a.begin(), a.end());
  172.    return a;
  173. }
  174.  
  175. vector<int> to_num(int s) {
  176.    vector<int> a;
  177.    while (s > 0) {
  178.        a.push_back(s % 10);
  179.        s /= 10;
  180.    }
  181.    return a;
  182. }
  183.  
  184. bool greater_(const vector<int>& lhs, const vector<int>& rhs) {
  185.    if (lhs.size() > rhs.size()) {
  186.        return true;
  187.    } else if (lhs.size() < rhs.size()) {
  188.        return false;
  189.    }
  190.    for (int i = lhs.size() - 1; i >= 0; --i) {
  191.        if (lhs[i] > rhs[i]) {
  192.            return true;
  193.        } else if (lhs[i] < rhs[i]) {
  194.            return false;
  195.        }
  196.    }
  197.    return false;
  198. }
  199.  
  200. int make2(int n) {
  201.    int pow = 2;
  202.    while (pow < n) {
  203.        pow *= 2;
  204.    }
  205.    return pow;
  206. }
  207.  
  208. void stripe(vector<int>& a) {
  209.    while (a.size() > 1 && a.back() == 0) {
  210.        a.pop_back();
  211.    }
  212. }
  213. pair<vector<int>, vector<int>> div21(vector<int> a, vector<int> b, int n);
  214. pair<vector<int>, vector<int>> div32(vector<int> a, vector<int> b, int n);
  215.  
  216. pair<vector<int>, vector<int>> div21(vector<int> a, vector<int> b, int n) {  //  del, chast
  217.    stripe(a);
  218.    stripe(b);
  219.    if (a.empty() || (a.size() == 1 && a[0] == 0)) {
  220.        return {{}, {}};
  221.    }
  222.    if (2 * n < 18) {
  223.        ll A = 0, B = 0;
  224.        for (int i = a.size() - 1; i >= 0; --i) {
  225.            A *= 10;
  226.            A += a[i];
  227.        }
  228.        for (int i = b.size() - 1; i >= 0; --i) {
  229.            B *= 10;
  230.            B += b[i];
  231.        }
  232.        return {to_num(A / B), to_num(A % B)};
  233.    }
  234.    vector<int> a1;
  235.    for (int i = n/2; i < a.size(); ++i) {
  236.        a1.push_back(a[i]);
  237.    }
  238.    // a = ... a1
  239.    auto [del1, ost1] = div32(a1, b, n / 2);
  240.    a.resize(n/2 + ost1.size());
  241.    for (int i = 0; i < ost1.size(); ++i) {
  242.        a[i + n / 2] = ost1[i];
  243.    }
  244.    auto [del2, ost2] = div32(a, b, n / 2);
  245.    del2.resize(n / 2 + del1.size());
  246.    for (int i = 0; i < del1.size(); ++i) {
  247.        del2[n / 2 + i] = del1[i];
  248.    }
  249.    return {del2, ost2};
  250. }
  251.  
  252. bool minus_(vector<int>& a, vector<int> b) {  //  true if plus
  253.    stripe(a);
  254.    stripe(b);
  255.    if (greater_(a, b) || equal(a.begin(), a.end(), b.begin(), b.end())) {
  256.        bool f = false;
  257.        for (int i = 0; i < b.size(); ++i) {
  258.            a[i] -= b[i] + f;
  259.            if (a[i] < 0) {
  260.                a[i] += 10;
  261.                f = true;
  262.            } else {
  263.                f = false;
  264.            }
  265.        }
  266.        int j = b.size();
  267.        while (f && j < a.size()) {
  268.            a[j] -= f;
  269.            if (a[j] < 0) {
  270.                a[j] += 10;
  271.                f = true;
  272.            } else {
  273.                f = false;
  274.            }
  275.            j++;
  276.        }
  277.        return true;
  278.    } else {
  279.        bool f = false;
  280.        swap(a, b);
  281.        for (int i = 0; i < b.size(); ++i) {
  282.            a[i] -= b[i] + f;
  283.            if (a[i] < 0) {
  284.                a[i] += 10;
  285.                f = true;
  286.            } else {
  287.                f = false;
  288.            }
  289.        }
  290.        int j = b.size();
  291.        while (f && j < a.size()) {
  292.            a[j] -= f;
  293.            if (a[j] < 0) {
  294.                a[j] += 10;
  295.                f = true;
  296.            } else {
  297.                f = false;
  298.            }
  299.            j++;
  300.        }
  301.        return false;
  302.    }
  303. }
  304.  
  305. bool plus_(vector<int>& a, vector<int> b) {  // -a + b
  306.    stripe(a);
  307.    stripe(b);
  308.    bool f = minus_(b, a);
  309.    swap(a, b);
  310.    return f;
  311. }
  312.  
  313. void dec_(vector<int>& a) { // a--
  314.    for (int i = 0; i < a.size(); ++i) {
  315.        if (a[i] == 0) {
  316.            a[i] = 9;
  317.        } else {
  318.            --a[i];
  319.            break;
  320.        }
  321.    }
  322.    while (a.size() > 1 && a.back() == 0) {
  323.        a.pop_back();
  324.    }
  325. }
  326.  
  327. void inc_(vector<int>& a) { //  a++
  328.    int carry = 1;
  329.    for (int & i : a) {
  330.        i += carry;
  331.        if (i >= 10) {
  332.            carry = 1;
  333.            i -= 10;
  334.        } else {
  335.            carry = 0;
  336.            break;
  337.        }
  338.    }
  339.    if (carry) {
  340.        a.push_back(1);
  341.    }
  342. }
  343.  
  344. vector<int> subl(const vector<int>& A) {  //  a * 2
  345.    vector<int> a = A;
  346.    int carry = 0;
  347.    for (int & i : a) {
  348.        i += carry;
  349.        i *= 2;
  350.        if (i >= 10) {
  351.            carry = 1;
  352.            i -= 10;
  353.        } else {
  354.            carry = 0;
  355.        }
  356.    }
  357.    if (carry) {
  358.        a.push_back(1);
  359.    }
  360.    return a;
  361. }
  362.  
  363. pair<vector<int>, vector<int>> div32(vector<int> a, vector<int> b, int n) {
  364.    stripe(a);
  365.    stripe(b);
  366.    if (a.empty() || (a.size() == 1 && a[0] == 0)) {
  367.        return {{}, {}};
  368.    }
  369.    if (3 * n < 18) {
  370.        ll A = 0, B = 0;
  371.        for (int i = a.size() - 1; i >= 0; --i) {
  372.            A *= 10;
  373.            A += a[i];
  374.        }
  375.        for (int i = b.size() - 1; i >= 0; --i) {
  376.            B *= 10;
  377.            B += b[i];
  378.        }
  379.        return {to_num(A / B), to_num(A % B)};
  380.    }
  381.    if (a.size() <= 2 * n && b.size() <= n) {
  382.        return div21(a, b, n);
  383.    }
  384.    assert(b.size() > n);
  385.    vector<int> b1;
  386.    for (int i = b.size() - n; i < b.size(); ++i) {
  387.        b1.push_back(b[i]);
  388.    }
  389.    vector<int> a1;
  390.    for (int i = b.size() - n; i < a.size(); ++i) {
  391.        a1.push_back(a[i]);
  392.    }
  393.    vector<int> b2;
  394.    for (int i = 0; i < n; ++i){
  395.        b2.push_back(0);
  396.    }
  397.    for (auto i : b1) {
  398.        b2.push_back(i);
  399.    }
  400.    vector<int> del1, ost1;
  401.    if (greater_(a1, b2)) {
  402.        //  b1 * 2 и все будет ок
  403. //        auto ii = div21(a1, subl(b1), n);
  404. //        del1 = subl(ii.first);
  405. //        ost1 = subl(ii.second);
  406. //        bool f = minus_(ost1, b);
  407. //        while (f) {
  408. //            inc_(del1);
  409. //            f = minus_(ost1, b);
  410. //        }
  411.        for (int i = 0; i < n; ++i) {
  412.            del1.push_back(9);
  413.        }
  414.    } else {
  415.        auto ii = div21(a1, b1, n);
  416.        del1 = ii.first;
  417.        ost1 = ii.second;
  418.    }
  419.    bool f = minus_(a, mulFFT(b, del1));
  420.    while (!f) {
  421.        f = plus_(a, b);
  422.        dec_(del1);
  423.    }
  424.    return {del1, a};
  425. }
  426.  
  427. void solve() {
  428.    initFFT();
  429.    string a, b;
  430.    cin >> a >> b;
  431.    if (a.length() < b.length()) {
  432.        cout << 0 << endl;
  433.        return;
  434.    }
  435.    vector<int> first_num = to_num(a);
  436.    vector<int> second_num = to_num(b);
  437.    if (greater_(second_num, first_num)) {
  438.        cout << 0 << endl;
  439.        return;
  440.    }
  441.    int n = make2(int(a.size()));
  442.    auto [r1, r2] = div21(first_num, second_num, n);
  443.    stripe(r1);
  444.    for (int i = r1.size() - 1; i >= 0; --i) {
  445.        cout << r1[i];
  446.    }
  447.    cout << endl;
  448.  
  449. }
  450.  
  451. int32_t main() {
  452.    ios_base::sync_with_stdio(false);
  453.    cin.tie(NULL);
  454.    cout.tie(NULL);
  455.    cout.precision(30);
  456.    int testCases = 1;
  457. #ifdef LOCAL
  458.    freopen("input.txt", "r", stdin);
  459.    //freopen("output.txt", "w", stdout);
  460.    cin >> testCases;
  461. #else
  462.    //freopen("inputik.txt", "r", stdin);
  463.    //freopen("outputik.txt", "w", stdout);
  464.    testCases = 1;
  465. #endif
  466.    while (testCases--) {
  467.        solve();
  468. #ifdef LOCAL
  469.        cout << "__________________________" << endl;
  470. #endif
  471.    }
  472. #ifdef LOCAL
  473.    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  474. #endif
  475.    return 0;
  476. }
  477.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!