Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
- #pragma GCC optimize("O3")
- #pragma GCC optimize("unroll-loops")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef pair<ull, ull> puu;
- typedef tree<int,
- null_type,
- less<int>,
- rb_tree_tag,
- tree_order_statistics_node_update> ordered_set;
- #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define file_in freopen("input.txt", "r", stdin);
- #define all(x) (x).begin(), (x).end()
- #define sz(x) (int)x.size()
- #define fi first;
- #define se second;
- template<typename T> istream& operator>>(istream& in, vector<T> &v) { for (auto &el : v) in >> el; return in; }
- template<typename T> ostream& operator<<(ostream& out, vector<T> &v) { for (auto &el : v) out << el << " "; return out; }
- template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2> &v) { in >> v.first >> v.second; return in; }
- template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> &v) { cout << v.first << " " << v.second; return out; }
- ll extgcd(ll a, ll b, ll &x, ll &y) {
- if (a == 0) {
- x = 0; y = 1;
- return b;
- }
- ll x1, y1;
- ll g = extgcd(b % a, a, x1, y1);
- x = y1 - (b / a) * x1;
- y = x1;
- return g;
- }
- int main() {
- fast
- // file_in
- ll a, b, c, x, y;
- cin >> a >> b >> c;
- ll g = extgcd(a, b, x, y);
- if (c % g != 0) {
- cout << "Impossible" << '\n';
- return 0;
- }
- x *= c / g;
- y *= c / g;
- ll da = b / g, db = a / g;
- while (x < 0) {
- x += da;
- y -= db;
- }
- while (x - da >= 0) {
- x -= da;
- y += db;
- }
- cout << x << " " << y << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement