Advertisement
libobil

Untitled

Oct 22nd, 2022
843
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.47 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <numeric>
  5. #include <vector>
  6. #include <cmath>
  7. #include <map>
  8.  
  9. #pragma GCC optimize("O3,unroll_loops")
  10. #pragma GCC target("sse4")
  11.  
  12. short base;
  13. inline std::vector <short> operator + (const std::vector <short>& a, const std::vector <short>& b)
  14. {
  15.     short prenos = 0;
  16.     std::vector <short> res;
  17.     for (short i = 0 ; i < std::max(a.size(), b.size()) || prenos ; ++i)
  18.     {
  19.         if (i < a.size()) prenos += a[i];
  20.         if (i < b.size()) prenos += b[i];
  21.         res.push_back(prenos % base);
  22.         prenos /= base;
  23.     }
  24.  
  25.     return res;
  26. }
  27.  
  28. inline std::vector <short> operator - (const std::vector <short>& a, const std::vector <short>& b)
  29. {
  30.     short prenos = 0;
  31.     std::vector <short> res = a;
  32.     for (short i = 0 ; i < a.size() && (prenos || i < b.size()) ; ++i)
  33.     {
  34.         if (i >= b.size())
  35.         {
  36.             if (a[i] == 0) continue;
  37.             res[i]--;
  38.             prenos = 0;
  39.         } else
  40.         {
  41.             if (a[i] >= b[i] + prenos)
  42.             {
  43.                 res[i] = a[i] - b[i] - prenos;
  44.                 prenos = 0;
  45.             } else
  46.             {
  47.                 res[i] = base + a[i] - b[i] - prenos;
  48.                 prenos = 1;
  49.             }
  50.         }
  51.     }
  52.  
  53.     while (res.size() >= 2 && res.back() == 0) res.pop_back();
  54.     return res;
  55. }
  56.  
  57. inline std::vector <short> operator * (const std::vector <short>& a, const std::vector <short>& b)
  58. {
  59.     std::vector <short> res;
  60.     res.resize((1 + a.size()) * (b.size() + 1), 0);
  61.     for (short i = 0 ; i < a.size() ; ++i)
  62.     {
  63.         short prenos = 0;
  64.         for (short j = 0 ; j < b.size() || prenos ; ++j)
  65.         {
  66.             if (j < b.size()) prenos += a[i] * b[j];
  67.             res[i + j] += prenos;
  68.             prenos = res[i + j] / base;
  69.             res[i + j] %= base;
  70.         }
  71.     }
  72.  
  73.     while (res.size() >= 2 && res.back() == 0) res.pop_back();
  74.     return res;
  75. }
  76.  
  77. inline std::vector <short> operator / (const std::vector <short>& a, short num)
  78. {
  79.     short prenos = 0;
  80.     std::vector <short> res;
  81.     for (short i = a.size() - 1 ; i >= 0 ; --i)
  82.     {
  83.         prenos *= base;
  84.         prenos += a[i];
  85.         res.push_back(prenos / num);
  86.         prenos %= num;
  87.     }
  88.  
  89.     std::reverse(res.begin(), res.end());
  90.     while (res.size() >= 2 && res.back() == 0) res.pop_back();
  91.     return res;
  92. }
  93.  
  94. inline short operator % (const std::vector <short>& a, short num)
  95. {
  96.     short prenos = 0;
  97.     for (short i = a.size() - 1 ; i >= 0 ; --i)
  98.     {
  99.         prenos *= base;
  100.         prenos += a[i];
  101.         prenos %= num;
  102.     }
  103.  
  104.     return prenos;
  105. }
  106.  
  107. inline bool operator <= (std::vector <short> a, std::vector <short> b)
  108. {
  109.     if (a.size() < b.size()) return true;
  110.     if (a.size() > b.size()) return false;
  111.    
  112.     for (short i = a.size() - 1 ; i >= 0 ; --i)
  113.     {
  114.         if (a[i] < b[i]) return true;
  115.         if (a[i] > b[i]) return false;
  116.     }
  117.  
  118.     return true;
  119. }
  120.  
  121. inline std::vector <short> operator / (const std::vector <short>& a, const std::vector <short>& b)
  122. {
  123.     std::vector <short> one = {1}, l = {0}, r = a + one, mid;
  124.     while (l + one != r)
  125.     {
  126.         mid = (l + r) / 2;
  127.         if (b * mid <= a) l = mid;
  128.         else r = mid;
  129.     }
  130.  
  131.     return l;
  132. }
  133.  
  134. inline void prshort(std::vector <short> v)
  135. {
  136.     for (short i = v.size() - 1 ; i >= 0 ; --i)
  137.     {
  138.         if (v[i] <= 9) std::cout << v[i];
  139.         else std::cout << char('A' + v[i] - 10);
  140.     }
  141. }
  142.  
  143.  
  144. inline std::vector <short> operator % (const std::vector <short>& a, const std::vector <short>& b)
  145. {
  146.     return a - ((a / b) * b);
  147. }
  148.  
  149. inline short getNum(char c)
  150. {
  151.     if ('0' <= c && c <= '9') return c - '0';
  152.     return c - 'A' + 10;
  153. }
  154.  
  155. inline std::vector <short> gcd(std::vector <short> a, std::vector <short> b)
  156. {
  157.     if (b.size() == 1 && b[0] == 0) return a;
  158.     return gcd(b, a % b);
  159. }
  160.  
  161. std::string a, b;
  162. struct Fraction
  163. {
  164.     std::vector <short> p, q;
  165.     Fraction()
  166.     {
  167.         p = {0};
  168.         q = {1};
  169.     }
  170.  
  171.     Fraction(std::vector <short> _p, std::vector <short> _q)
  172.     {
  173.         p = _p;
  174.         q = _q;
  175.     }
  176.  
  177.     inline friend Fraction operator + (Fraction a, Fraction b)
  178.     {
  179.         Fraction res;
  180.         res.p = (a.p * b.q + b.p * a.q);
  181.         res.q = a.q * b.q;
  182.         std::vector <short> currgcd = gcd(res.p, res.q);
  183.         res.p = res.p / currgcd;
  184.         res.q = res.q / currgcd;
  185.         return res;
  186.     }
  187.  
  188.     Fraction(const std::string &input)
  189.     {
  190.         short where = 0;
  191.         std::vector <short> shorteger, fract, period;
  192.         for (const char &c : input)
  193.         {
  194.             if (c == ')') break;
  195.             if (c == '.' || c == '(')
  196.             {
  197.                 where++;
  198.                 continue;
  199.             }
  200.  
  201.             if (where == 0) shorteger.push_back(getNum(c));
  202.             if (where == 1) fract.push_back(getNum(c));
  203.             if (where == 2) period.push_back(getNum(c));
  204.         }
  205.  
  206.         Fraction res;
  207.         std::vector <short> currBase, vectorBase;
  208.         vectorBase.push_back(0);
  209.         vectorBase.push_back(1);
  210.         currBase = vectorBase;
  211.  
  212.         for (const short &i : shorteger)
  213.         {
  214.             std::vector <short> curr = {i};
  215.             res.p = res.p * vectorBase;
  216.             res.p = res.p + curr;
  217.         }
  218.  
  219.         for (const short &i : fract)
  220.         {
  221.             Fraction curr;
  222.             curr.p = {i};
  223.             curr.q = currBase;
  224.             res = res + curr;
  225.             currBase = currBase * vectorBase;
  226.         }
  227.  
  228.         currBase = currBase / vectorBase;
  229.         std::vector <short> minusOne;
  230.         minusOne.push_back(base - 1);
  231.         currBase = currBase * minusOne;
  232.        
  233.         Fraction curr;
  234.         curr.p.clear();
  235.         curr.q.clear();
  236.         for (short i = 0 ; i < fract.size() ; ++i) curr.q.push_back(0);
  237.         for (const short &i : period)
  238.         {
  239.             curr.p.push_back(i);
  240.             curr.q.push_back(base - 1);
  241.         }
  242.  
  243.         std::reverse(curr.p.begin(), curr.p.end());
  244.         if (!curr.p.empty()) res = res + curr;
  245.         p = res.p;
  246.         q = res.q;
  247.     }
  248. };
  249.  
  250. std::vector <short> here;
  251. std::map <std::vector <short>, short> mp;
  252. void solve()
  253. {
  254.     Fraction left(a);
  255.     Fraction right(b);
  256.     Fraction res = left + right;
  257.     std::vector <short> vectorBase; vectorBase.push_back(0); vectorBase.push_back(1);
  258.     std::vector <short> div = res.p / res.q;
  259.     std::vector <short> rem = res.p % res.q;
  260.     std::vector <short> zero; zero.push_back(0);
  261.     if (rem == zero)
  262.     {
  263.         prshort(div);
  264.         return;
  265.     }
  266.  
  267.     for (short i = 0 ; rem != zero ; ++i)
  268.     {
  269.         if (mp.count(rem)) break;
  270.         mp[rem] = i;
  271.         rem = rem * vectorBase;
  272.         std::vector <short> divided = (rem / res.q);
  273.         here.push_back(divided[0]);
  274.         rem = rem % res.q;
  275.     }
  276.  
  277.     short pos = -1;
  278.     if (rem != zero) pos = mp[rem];
  279.     prshort(div);
  280.     std::cout << '.';
  281.     for (short i = 0 ; i < here.size() ; ++i)
  282.     {
  283.         if (i == pos) std::cout << '(';
  284.         if (here[i] <= 9) std::cout << here[i];
  285.         else std::cout << char('A' + here[i] - 10);
  286.     }
  287.  
  288.     if (pos != -1) std::cout << ')';
  289.     std::cout << '\n';
  290. }
  291.  
  292. void read()
  293. {
  294.     std::cin >> base;
  295.     std::cin >> a >> b;
  296. }
  297.  
  298. void fastIO()
  299. {
  300.     std::ios_base :: sync_with_stdio(0);
  301.     std::cout.tie(nullptr);
  302.     std::cin.tie(nullptr);
  303. }
  304.  
  305. int main()
  306. {
  307.     fastIO();
  308.     read();
  309.     solve();
  310.  
  311.     return 0;
  312. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement