Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <iomanip>
- #include <numeric>
- #include <vector>
- #include <cmath>
- #include <map>
- #pragma GCC optimize("O3,unroll_loops")
- #pragma GCC target("sse4")
- short base;
- inline std::vector <short> operator + (const std::vector <short>& a, const std::vector <short>& b)
- {
- short prenos = 0;
- std::vector <short> res;
- for (short i = 0 ; i < std::max(a.size(), b.size()) || prenos ; ++i)
- {
- if (i < a.size()) prenos += a[i];
- if (i < b.size()) prenos += b[i];
- res.push_back(prenos % base);
- prenos /= base;
- }
- return res;
- }
- inline std::vector <short> operator - (const std::vector <short>& a, const std::vector <short>& b)
- {
- short prenos = 0;
- std::vector <short> res = a;
- for (short i = 0 ; i < a.size() && (prenos || i < b.size()) ; ++i)
- {
- if (i >= b.size())
- {
- if (a[i] == 0) continue;
- res[i]--;
- prenos = 0;
- } else
- {
- if (a[i] >= b[i] + prenos)
- {
- res[i] = a[i] - b[i] - prenos;
- prenos = 0;
- } else
- {
- res[i] = base + a[i] - b[i] - prenos;
- prenos = 1;
- }
- }
- }
- while (res.size() >= 2 && res.back() == 0) res.pop_back();
- return res;
- }
- inline std::vector <short> operator * (const std::vector <short>& a, const std::vector <short>& b)
- {
- std::vector <short> res;
- res.resize((1 + a.size()) * (b.size() + 1), 0);
- for (short i = 0 ; i < a.size() ; ++i)
- {
- short prenos = 0;
- for (short j = 0 ; j < b.size() || prenos ; ++j)
- {
- if (j < b.size()) prenos += a[i] * b[j];
- res[i + j] += prenos;
- prenos = res[i + j] / base;
- res[i + j] %= base;
- }
- }
- while (res.size() >= 2 && res.back() == 0) res.pop_back();
- return res;
- }
- inline std::vector <short> operator / (const std::vector <short>& a, short num)
- {
- short prenos = 0;
- std::vector <short> res;
- for (short i = a.size() - 1 ; i >= 0 ; --i)
- {
- prenos *= base;
- prenos += a[i];
- res.push_back(prenos / num);
- prenos %= num;
- }
- std::reverse(res.begin(), res.end());
- while (res.size() >= 2 && res.back() == 0) res.pop_back();
- return res;
- }
- inline short operator % (const std::vector <short>& a, short num)
- {
- short prenos = 0;
- for (short i = a.size() - 1 ; i >= 0 ; --i)
- {
- prenos *= base;
- prenos += a[i];
- prenos %= num;
- }
- return prenos;
- }
- inline bool operator <= (std::vector <short> a, std::vector <short> b)
- {
- if (a.size() < b.size()) return true;
- if (a.size() > b.size()) return false;
- for (short i = a.size() - 1 ; i >= 0 ; --i)
- {
- if (a[i] < b[i]) return true;
- if (a[i] > b[i]) return false;
- }
- return true;
- }
- inline std::vector <short> operator / (const std::vector <short>& a, const std::vector <short>& b)
- {
- std::vector <short> one = {1}, l = {0}, r = a + one, mid;
- while (l + one != r)
- {
- mid = (l + r) / 2;
- if (b * mid <= a) l = mid;
- else r = mid;
- }
- return l;
- }
- inline void prshort(std::vector <short> v)
- {
- for (short i = v.size() - 1 ; i >= 0 ; --i)
- {
- if (v[i] <= 9) std::cout << v[i];
- else std::cout << char('A' + v[i] - 10);
- }
- }
- inline std::vector <short> operator % (const std::vector <short>& a, const std::vector <short>& b)
- {
- return a - ((a / b) * b);
- }
- inline short getNum(char c)
- {
- if ('0' <= c && c <= '9') return c - '0';
- return c - 'A' + 10;
- }
- inline std::vector <short> gcd(std::vector <short> a, std::vector <short> b)
- {
- if (b.size() == 1 && b[0] == 0) return a;
- return gcd(b, a % b);
- }
- std::string a, b;
- struct Fraction
- {
- std::vector <short> p, q;
- Fraction()
- {
- p = {0};
- q = {1};
- }
- Fraction(std::vector <short> _p, std::vector <short> _q)
- {
- p = _p;
- q = _q;
- }
- inline friend Fraction operator + (Fraction a, Fraction b)
- {
- Fraction res;
- res.p = (a.p * b.q + b.p * a.q);
- res.q = a.q * b.q;
- std::vector <short> currgcd = gcd(res.p, res.q);
- res.p = res.p / currgcd;
- res.q = res.q / currgcd;
- return res;
- }
- Fraction(const std::string &input)
- {
- short where = 0;
- std::vector <short> shorteger, fract, period;
- for (const char &c : input)
- {
- if (c == ')') break;
- if (c == '.' || c == '(')
- {
- where++;
- continue;
- }
- if (where == 0) shorteger.push_back(getNum(c));
- if (where == 1) fract.push_back(getNum(c));
- if (where == 2) period.push_back(getNum(c));
- }
- Fraction res;
- std::vector <short> currBase, vectorBase;
- vectorBase.push_back(0);
- vectorBase.push_back(1);
- currBase = vectorBase;
- for (const short &i : shorteger)
- {
- std::vector <short> curr = {i};
- res.p = res.p * vectorBase;
- res.p = res.p + curr;
- }
- for (const short &i : fract)
- {
- Fraction curr;
- curr.p = {i};
- curr.q = currBase;
- res = res + curr;
- currBase = currBase * vectorBase;
- }
- currBase = currBase / vectorBase;
- std::vector <short> minusOne;
- minusOne.push_back(base - 1);
- currBase = currBase * minusOne;
- Fraction curr;
- curr.p.clear();
- curr.q.clear();
- for (short i = 0 ; i < fract.size() ; ++i) curr.q.push_back(0);
- for (const short &i : period)
- {
- curr.p.push_back(i);
- curr.q.push_back(base - 1);
- }
- std::reverse(curr.p.begin(), curr.p.end());
- if (!curr.p.empty()) res = res + curr;
- p = res.p;
- q = res.q;
- }
- };
- std::vector <short> here;
- std::map <std::vector <short>, short> mp;
- void solve()
- {
- Fraction left(a);
- Fraction right(b);
- Fraction res = left + right;
- std::vector <short> vectorBase; vectorBase.push_back(0); vectorBase.push_back(1);
- std::vector <short> div = res.p / res.q;
- std::vector <short> rem = res.p % res.q;
- std::vector <short> zero; zero.push_back(0);
- if (rem == zero)
- {
- prshort(div);
- return;
- }
- for (short i = 0 ; rem != zero ; ++i)
- {
- if (mp.count(rem)) break;
- mp[rem] = i;
- rem = rem * vectorBase;
- std::vector <short> divided = (rem / res.q);
- here.push_back(divided[0]);
- rem = rem % res.q;
- }
- short pos = -1;
- if (rem != zero) pos = mp[rem];
- prshort(div);
- std::cout << '.';
- for (short i = 0 ; i < here.size() ; ++i)
- {
- if (i == pos) std::cout << '(';
- if (here[i] <= 9) std::cout << here[i];
- else std::cout << char('A' + here[i] - 10);
- }
- if (pos != -1) std::cout << ')';
- std::cout << '\n';
- }
- void read()
- {
- std::cin >> base;
- std::cin >> a >> b;
- }
- void fastIO()
- {
- std::ios_base :: sync_with_stdio(0);
- std::cout.tie(nullptr);
- std::cin.tie(nullptr);
- }
- int main()
- {
- fastIO();
- read();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement