fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define ln '\n'
  5. #define umap unordered_map
  6. #define uset unordered_set
  7. #define prqueue priority_queue
  8. #define H ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  9. #define io freopen("once.in", "r", stdin);freopen("once.out", "w", stdout);
  10. using namespace std;
  11. const ll mod = 1000000007;
  12. const ll N = 5e18;
  13. int vid;
  14.  
  15. void shft(ll a, ll b, ll& x, ll& y, ll cnt){
  16. 	x += cnt * b;
  17. 	y -= cnt * a;
  18. }
  19.  
  20. ll gcd(ll a, ll b, ll& x, ll& y){
  21. 	if (!b){
  22. 		x = 1, y = 0;
  23. 		return a;
  24. 	}
  25. 	ll g = gcd(b, a % b, y, x);
  26. 	y -= x * (a / b);
  27. 	return g;
  28. }
  29.  
  30. bool solve(ll a, ll b, ll& m1, ll& m2, ll c, ll& c1, ll& c2){
  31. 	ll x = m1, y = m2;
  32. 	ll g = gcd(a, b, x, y);
  33. 	if (c % g) return 0;
  34. 	a /= g;
  35. 	b /= g;
  36. 	x *= c / g;
  37. 	y *= c / g;
  38.  
  39. 	shft(a, b, x, y, -x / b);
  40. 	if (x < 0) shft(a, b, x, y, 1);
  41.  
  42. 	ll tmpx = x, tmpy = y;
  43.  
  44. 	shft(a, b, x, y, y / a);
  45. 	if (y < 0) shft(a, b, x, y, -1);
  46.  
  47. 	if (c1 * x + c2 * y < c1 * tmpx + c2 * tmpy) m1 = x, m2 = y;
  48. 	else m1 = tmpx, m2 = tmpy;
  49. 	return 1;
  50. }
  51.  
  52. int main() {
  53.     H
  54.     ll n;
  55.     while (cin >> n, n){
  56.     	ll c1, n1, c2, n2;
  57.     	cin >> c1 >> n1 >> c2 >> n2;
  58.     	ll m1, m2;
  59.     	if (!solve(n1, n2, m1, m2, n, c1, c2)) cout << "failed";
  60.     	else cout << m1 << ' ' << m2;
  61.     	cout << ln;
  62.     }
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
13
1 10
1 7
0
stdout
copy 
2 -1
https://ideone.com/jnMP6L
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!