fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. ll gcd(ll a, ll b, ll& x, ll& y) {
  6.     if (b == 0) {
  7.         x = 1;
  8.         y = 0;
  9.         return a;
  10.     }
  11.     ll x1, y1;
  12.     ll d = gcd(b, a % b, x1, y1);
  13.     x = y1;
  14.     y = x1 - y1 * (a / b);
  15.     return d;
  16. }
  17.  
  18. bool find_any_solution(ll a, ll b, ll c, ll &x0, ll &y0, ll &g) {
  19.     g = gcd(abs(a), abs(b), x0, y0);
  20.     if (c % g)
  21.         return false;
  22.     x0 *= c / g;
  23.     y0 *= c / g;
  24.     ll lcm = a / g * b;
  25.     x0 = x0 * a;
  26.     y0 = y0 * b;
  27.     if(x0 < 0) {
  28.         ll delta = (abs(x0) / lcm + (abs(x0) % lcm != 0)) * lcm;
  29.         x0 += delta;
  30.         y0 -= delta;
  31.     }
  32.     else if(y0 < 0) {
  33.         ll delta = (abs(y0) / lcm + (abs(y0) % lcm != 0)) * lcm;
  34.         x0 -= delta;
  35.         y0 += delta;
  36.     }
  37.     x0 /= a;
  38.     y0 /= b;
  39.     if(x0 < 0 || y0 < 0)
  40.         return false;
  41.     return true;
  42. }
  43.  
  44.  
  45. int main() {
  46.     int t;
  47.     cin>>t;
  48.     while(t--) {
  49.         ll n, n1, n2, a, b;
  50.         cin>>n>>a>>n1>>b>>n2;
  51.         ll x, y, g;
  52.         if(!find_any_solution(n1, n2, n, x, y, g)) {
  53.             cout<<"failed\n";
  54.         }
  55.         else {
  56.             ll ax = n1 * x;
  57.             ll bx = n2 * y;
  58.             ll lcm = n1 / g * n2;
  59.             if(n1 * b < n2 * a) {
  60.                 ll delta = (ax / lcm) * lcm;
  61.                 ax -= delta; bx += delta;
  62.                 cout<<(ax / n1)<<" "<<(bx / n2)<<"\n";
  63.             }
  64.             else {
  65.                 ll delta = (bx / lcm) * lcm;
  66.                 ax += delta; bx -= delta;
  67.                 cout<<(ax / n1)<<" "<<(bx / n2)<<"\n";
  68.             }
  69.         }
  70.     }
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/O1S8Bi
language:
C++14 (gcc 8.3)
created:
3 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!