Advertisement
Guest User

Untitled

a guest
Mar 17th, 2017
404
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, c1, n1, c2, n2;
  5.  
  6. int gcd(int a, int b, long long& x, long long& y) {
  7.     if (b == 0) {
  8.         x = 1, y = 0;
  9.         return a;
  10.     }
  11.     int ret = gcd(b, a % b, x, y);
  12.     int x1, y1;
  13.     x1 = y;
  14.     y1 = x - (a / b) * y;
  15.     x = x1;
  16.     y = y1;
  17.     return ret;
  18. }
  19.  
  20.  
  21. int main() {
  22.     while (cin >> n && n > 0) {
  23.         bool s = false;
  24.         cin >> c1 >> n1 >> c2 >> n2;
  25.         int a = n1, b = n2;
  26.         long long x, y;
  27.         int g = gcd(n1, n2, x, y);
  28.         if (n % g > 0) cout << "failed" << endl;
  29.         else if (x < 0 && y < 0) cout << "failed" << endl;
  30.         else {
  31.             int t = n / g;
  32.             x *= t;
  33.             y *= t;
  34.             if (x >= 0 && y >= 0) {
  35.                 if (c1 * b > c2 * a) swap(a, b), swap(x, y), swap(c1, c2), s = true;
  36.                 long long l = y / (a / g);
  37.                 x += l * (b / g);
  38.                 y -= l * (a / g);
  39.                 assert(y >= 0);
  40.                 if (s) swap(x, y);
  41.                 cout << x << " " << y << endl;
  42.             } else if (x < 0 && y >= 0) {
  43.                 long long l = y / (a / g);
  44.                 x += l * (b / g);
  45.                 y -= l * (a / g);
  46.                 if (x < 0) cout << "failed" << endl;
  47.                 else {
  48.                     if (c1 * b > c2 * a) swap(a, b), swap(x, y), swap(c1, c2), s = true;
  49.                     l = y / (a / g);
  50.                     x += l * (b / g);
  51.                     y -= l * (a / g);
  52.                     assert(y >= 0);
  53.                     if (s) swap(x, y);
  54.                     cout << x << " " << y << endl;
  55.                 }      
  56.             } else if (x >= 0 && y < 0) {
  57.                 long long l = x / (b / g);
  58.                 x -= l * (b / g);
  59.                 y += l * (a / g);
  60.                 if (y < 0) cout << "failed" << endl;
  61.                 else {
  62.                     if (c1 * b > c2 * a) swap(a, b), swap(x, y), swap(c1, c2), s = true;
  63.                     l = y / (a / g);
  64.                     x += l * (b / g);
  65.                     y -= l * (a / g);
  66.                     assert(y >= 0);
  67.                     if (s) swap(x, y);
  68.                     cout << x << " " << y << endl;
  69.                 }
  70.             }
  71.         }          
  72.     }
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement