MathQ_

Untitled

Jan 14th, 2022
929
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
  2. #pragma GCC optimize("O3")
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12. typedef unsigned long long ull;
  13. typedef long long ll;
  14. typedef long double ld;
  15. typedef pair<int, int> pii;
  16. typedef pair<ll, ll> pll;
  17. typedef pair<ull, ull> puu;
  18. typedef tree<int,
  19.              null_type,
  20.              less<int>,
  21.              rb_tree_tag,
  22.              tree_order_statistics_node_update> ordered_set;
  23.  
  24. #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  25. #define file_in freopen("input.txt", "r", stdin);
  26. #define all(x) (x).begin(), (x).end()
  27. #define sz(x) (int)x.size()
  28. #define fi first;
  29. #define se second;
  30.              
  31. template<typename T> istream& operator>>(istream& in, vector<T> &v) { for (auto &el : v) in >> el; return in; }
  32. template<typename T> ostream& operator<<(ostream& out, vector<T> &v) { for (auto &el : v) out << el << " "; return out; }
  33. template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2> &v) { in >> v.first >> v.second; return in; }
  34. template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> &v) { cout << v.first << " " << v.second; return out; }
  35.  
  36. ll extgcd(ll a, ll b, ll &x, ll &y) {
  37.     if (a == 0) {
  38.         x = 0; y = 1;
  39.         return b;
  40.     }
  41.     ll x1, y1;
  42.     ll g = extgcd(b % a, a, x1, y1);
  43.     x = y1 - (b / a) * x1;
  44.     y = x1;
  45.     return g;
  46. }
  47.  
  48. int main() {
  49.     fast
  50.     // file_in
  51.  
  52.     ll a, b, c, x, y;
  53.     cin >> a >> b >> c;
  54.     ll g = extgcd(a, b, x, y);
  55.     if (c % g != 0) {
  56.         cout << "Impossible" << '\n';
  57.         return 0;
  58.     }
  59.     x *= c / g;
  60.     y *= c / g;
  61.     ll da = b / g, db = a / g;
  62.    
  63.     while (x < 0) {
  64.         x += da;
  65.         y -= db;
  66.     }
  67.     while (x - da >= 0) {
  68.         x -= da;
  69.         y += db;
  70.     }
  71.     cout << x << " " << y << '\n';
  72.     return 0;
  73. }
RAW Paste Data