Guest User

goturen peyserdi

a guest
Apr 26th, 2019
85
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