Advertisement
double_trouble

gcd_ext

Oct 3rd, 2015
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <string.h>
  7.  
  8. #define F first
  9. #define S second
  10.  
  11. using namespace std;
  12.  
  13. int f;
  14.  
  15. int gcd(int x, int y)
  16. {
  17.     while (x != 0 && y != 0)
  18.      {
  19.          if (x > y)
  20.             x %= y;
  21.          else
  22.             y %= x;
  23.      }
  24.     return x + y;
  25. }
  26.  
  27. void gcd_ext(int a, int b, int &x, int &y)
  28. {
  29.     if (a < b)
  30.         swap(a, b);
  31.     if (b == 0)
  32.     {
  33.         x = 1;
  34.         y = 1;
  35.         return;
  36.     }
  37.     int x1, y1;
  38.     gcd_ext(b, a % b, x1, y1);
  39.     x = y1;
  40.     y = x1 - y1 * f;
  41. }
  42.  
  43. int main()
  44. {
  45.     ios_base::sync_with_stdio(0);
  46.     cin.tie(0);
  47.     cout.tie(0);
  48.     freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  49.     //freopen("console.in", "r", stdin);freopen("console.out", "w", stdout);
  50.  
  51.     int a, b, c;
  52.     cin >> a >> b >> c;
  53.     int g = gcd(a, b);
  54.     if (c % g > 0)
  55.     {
  56.         cout << "No solution" << endl;
  57.         return 0;
  58.     }
  59.  
  60.     f = a / b;
  61.  
  62.     int x, y;
  63.     gcd_ext(a, b, x, y);
  64.  
  65.     x *= c / g;
  66.     y *= c / g;
  67.  
  68.     cout << x << " " << y << endl;
  69.  
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement