Advertisement
Ikmik

cubic

Nov 6th, 2016
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cstring>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <stack>
  9. #include <queue>
  10. #include <deque>
  11. #include <algorithm>
  12. #include <sstream>
  13. #include <cstdlib>
  14. #include <cmath>
  15. #include <random>
  16. #include <bitset>
  17. #include <cassert>
  18. #include <tuple>
  19. #include <list>
  20. #include <iterator>
  21. #include <unordered_set>
  22. #include <unordered_map>
  23.  
  24. using namespace std;
  25.  
  26. typedef long long ll;
  27. typedef long double ld;
  28.  
  29. #define mp make_pair
  30. #define pb push_back
  31. #define mt make_tuple
  32.  
  33. #define forn(i, n) for (int i = 0; i < ((int)(n)); ++i)
  34. #define forrn(i, s, n) for (int i = (int)(s); i < ((int)(n)); ++i)
  35. #define all(v) (v).begin(), (v).end()
  36. #define rall(v) (v).rbegin(), (v).rend()
  37.  
  38. const int INF = 1791791791;
  39. const ll INFLL = 1791791791791791791ll;
  40.  
  41. struct fraction {
  42.     ll p, q;
  43.     fraction() {
  44.         p = 0;
  45.         q = 1;
  46.     }
  47.     fraction(ll _p, ll _q) {
  48.         //ll g = __gcd(_p, _q);
  49.         ll g = 1;
  50.         p = abs(_p / g);
  51.         q = abs(_q / g);
  52.         if ((_p < 0) ^ (_q < 0))
  53.             p = -p;
  54.     }
  55.     fraction(ll x) {
  56.         p = x;
  57.         q = 1;
  58.     }
  59. };
  60.  
  61. fraction operator+(const fraction& f, const fraction& s) {
  62.     return fraction(f.p * s.q + f.q * s.p, f.q * s.q);
  63. }
  64.  
  65. fraction operator*(const fraction& f, const fraction& s) {
  66.     return fraction(f.p * s.p, f.q * s.q);
  67. }
  68.  
  69. bool operator==(const fraction& f, const fraction& s) {
  70.     return f.q * s.p == f.p * s.q;
  71. }
  72.  
  73. bool operator<(const fraction& f, const fraction& s) {
  74.     return f.p * s.q < f.q * s.p;
  75. }
  76.  
  77. istream& operator>>(istream& is, fraction& f) {
  78.     is >> f.p >> f.q;
  79.     return is;
  80. }
  81.  
  82. ostream& operator<<(ostream& os, const fraction& f) {
  83.     ll g = __gcd(f.p, f.q);
  84.     os << f.p / g << "/" << f.q / g;
  85.     return os;
  86. }
  87.  
  88. template<class t>
  89. t fpow(t a, int n) {
  90.     if (n == 0)
  91.         return 1;
  92.     else if (n & 1)
  93.         return a * fpow(a, n ^ 1);
  94.     else {
  95.         t tmp = fpow(a, n >> 1);
  96.         return tmp * tmp;
  97.     }
  98. }
  99.  
  100. const int max_pow = 10;
  101. ll p2[max_pow + 1];
  102. ll p3[max_pow + 1];
  103.  
  104. int ify(char c) {
  105.     if (c == '0')
  106.         return 0;
  107.     else if (c == '-')
  108.         return -1;
  109.     else
  110.         return 1;
  111. }
  112.  
  113. void solve() {
  114.     char as; ll a1, a2; fraction a;
  115.     char bs; ll b1, b2; fraction b;
  116.     char cs; ll c1, c2; fraction c;
  117.     char ds; ll d1, d2; fraction d;
  118.     cin >> as >> a1 >> a2; a = ify(as) * fraction(p2[a1], p3[a2]); a1 = max(a1, -a1);
  119.     cin >> bs >> b1 >> b2; b = ify(bs) * fraction(b1, p3[b2]);
  120.     cin >> cs >> c1 >> c2; c = ify(cs) * fraction(c1, p3[c2]);
  121.     cin >> ds >> d1 >> d2; d = ify(ds) * fraction(p2[d1], p3[d2]); d1 = max(d1, -d1);
  122.  
  123.     vector<fraction> vec;
  124.  
  125.     for (ll s = -1; s <= 1; s += 2) {
  126.         forn(_p2, d1 + 1) {
  127.             forn(q2, a1 + 1) {
  128.                 forn(_p3, max(max(a2, b2), max(c2, d2)) + 1) {
  129.                     forn(q3, max(max(a2, b2), max(c2, d2)) + 1) {
  130.                         ll p = s * p2[_p2] * p3[_p3];
  131.                         ll q = p2[q2] * p3[q3];
  132.                         fraction f(p, q);
  133.                         if (a * fpow(f, 3) + b * fpow(f, 2) + c * f + d == 0)
  134.                             vec.pb(f);
  135.                     }
  136.                 }
  137.             }
  138.         }
  139.     }
  140.  
  141.     sort(all(vec));
  142.     vec.resize(distance(vec.begin(), unique(all(vec))));
  143.  
  144.     cout << vec.size() << " ";
  145.     for (auto f : vec)
  146.         cout << f << " ";
  147.     cout << endl;
  148. }
  149.  
  150. int main() {
  151.     ios_base::sync_with_stdio(false);
  152.     cin.tie(0);
  153.     cout.tie(0);
  154.     // Code here:
  155.    
  156.     forn(i, max_pow + 1) {
  157.         p2[i] = fpow(2ll, i);
  158.         p3[i] = fpow(3ll, i);
  159.     }
  160.  
  161.     int t;
  162.     cin >> t;
  163.     forn(i, t)
  164.         solve();    
  165.  
  166.     return 0;
  167. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement