Advertisement
ivnikkk

Untitled

May 26th, 2022
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS 
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(a) a.begin(), a.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef long double ld;
  9. ll gcd_ext(ll a, ll b, ll& x, ll& y) {
  10.     if (a == 0) {
  11.         x = 0, y = 1;
  12.         return b;
  13.     }
  14.     ll x1, y1;
  15.     ll d = gcd_ext(b % a, a, x1, y1);
  16.     x = y1 - (b / a) * x1;
  17.     y = x1;
  18.     return d;
  19. }
  20. bool solver(ll a, ll b, ll c, ll a2, ll b2, pll& ans) {
  21.     ll x, y;
  22.     ll g = gcd_ext(abs(a), abs(b), x, y);
  23.     if (c % g != 0) {
  24.         return false;
  25.     }
  26.     x *= c / g;
  27.     y *= c / g;
  28.     y *= -1;
  29.     ll d = b / g;
  30.     ll d2 = a / g;
  31.     // X = |b|*(y - d2 * k) + b2;
  32.     //X = |b|y+b2 - d2 * |b| * K
  33.  
  34.     ll x0 = (y * abs(b) + b2);
  35.     ll f = -d2 * abs(b);
  36.     if (f < 0) {
  37.         f *= -1;
  38.     //  if(x0<0)x0 *= -1;
  39.     }
  40.     //f *= -1;
  41.     x0 = (x0 % abs(f) + abs(f)) % abs(f);
  42.     ans = { x0, f };
  43.     return true;
  44. }
  45. signed main() {
  46. #ifdef _DEBUG
  47.     freopen("input.txt", "r", stdin);
  48.     freopen("output.txt", "w", stdout);
  49. #endif
  50.     freopen("chinese.in", "r", stdin);
  51.     freopen("chinese.out", "w", stdout);
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(nullptr);
  54.     cout.tie(nullptr);
  55.     ll t;
  56.     cin >> t;
  57.     while (t--) {
  58.         ll a, b;
  59.         cin >> a >> b;
  60.         ll n, m;
  61.         cin >> n >> m;
  62.         pll ans;
  63.         bool is_solve = solver(n, -m, b - a, a, b, ans);
  64.         if (is_solve) {
  65.             cout << "YES " << ans.first << ' ' << ans.second << '\n';
  66.         }
  67.         else {
  68.             cout << "NO\n";
  69.         }
  70.     }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement