SHARE
TWEET

goturen peyserdi

a guest Apr 26th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*** author LEGEND ***/
  2. # include<bits/stdc++.h>
  3. using namespace std;
  4. # define ll long long
  5. # define ull unsigned long long
  6. # define _FastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  7. ll exgcd(ll a,ll b){
  8.     ll x0 = 1,x1 = 0,y0 = 0,y1 = 1;
  9.     ll q,r,c,a0 = a,b0 = b;
  10.     while(b){
  11.     q = a/b;
  12.     r = a%b;
  13.     a = b;
  14.     b = r;
  15.     c = x1, x1 = x0 - q * x1, x0 = c;
  16.     c = y1, y1 = y0 - q * y1, y0 = c;
  17.     }
  18.     int d = abs(x0)/b0;
  19.     if(x0 < 0){
  20.         x0 = x0 + (d + 1) * b0;
  21.         y0 = y0 - (d + 1) * a0;
  22.             }
  23.             if(x0 - b > 0){
  24.                 x0 = x0 - d * b0;
  25.                 y0 = y0 + d * a0;
  26.             }
  27.             cout << x0 << " " << y0 << endl;
  28.             return 0;
  29. }
  30. int main()
  31. {
  32.   _FastIO;
  33.   ll n,a,b;
  34.   cin >> n;
  35.   while(n--){
  36.     cin >> a >> b;
  37.     if(__gcd(a,b) != 1){
  38.         cout << "No Solution" << endl;
  39.         continue;
  40.     }
  41.     exgcd(a,b);
  42.   }
  43.   return 0;
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top