Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(l) cerr<<#l<<' '<<l<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef long double ld;
- ll gcd_ext(ll a, ll b, ll& x, ll& y) {
- if (a == 0) {
- x = 0, y = 1;
- return b;
- }
- ll x1, y1;
- ll d = gcd_ext(b % a, a, x1, y1);
- x = y1 - (b / a) * x1;
- y = x1;
- return d;
- }
- bool solver(ll a, ll b, ll c, ll a2, ll b2, pll& ans) {
- ll x, y;
- ll g = gcd_ext(abs(a), abs(b), x, y);
- if (c % g != 0) {
- return false;
- }
- x *= c / g;
- y *= c / g;
- y *= -1;
- ll d = b / g;
- ll d2 = a / g;
- // X = |b|*(y - d2 * k) + b2;
- //X = |b|y+b2 - d2 * |b| * K
- ll x0 = (y * abs(b) + b2);
- ll f = -d2 * abs(b);
- if (f < 0) {
- f *= -1;
- // if(x0<0)x0 *= -1;
- }
- //f *= -1;
- x0 = (x0 % abs(f) + abs(f)) % abs(f);
- ans = { x0, f };
- return true;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- freopen("chinese.in", "r", stdin);
- freopen("chinese.out", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- ll t;
- cin >> t;
- while (t--) {
- ll a, b;
- cin >> a >> b;
- ll n, m;
- cin >> n >> m;
- pll ans;
- bool is_solve = solver(n, -m, b - a, a, b, ans);
- if (is_solve) {
- cout << "YES " << ans.first << ' ' << ans.second << '\n';
- }
- else {
- cout << "NO\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement