fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long extGCD(long long a, long long b, long long &x, long long &y) {
  5.     if (b == 0) {
  6.         x = 1;
  7.         y = 0;
  8.         return a;
  9.     }
  10.     long long x1, y1;
  11.     long long g = extGCD(b, a % b, x1, y1);
  12.     x = y1;
  13.     y = x1 - (a / b) * y1;
  14.     return g;
  15. }
  16.  
  17. int main() {
  18.     ios_base::sync_with_stdio(0);
  19.     cin.tie(0);
  20.  
  21.     long long a1, b1, a2, b2;
  22.     cin >> a1 >> b1 >> a2 >> b2;
  23.  
  24.     if (a1 == 0 && a2 == 0) {
  25.         cout << "0 0";
  26.         return 0;
  27.     }
  28.  
  29.     if (a1 == 0) {
  30.         cout << "0 " << (b1 - b2) / a2;
  31.         return 0;
  32.     }
  33.  
  34.     if (a2 == 0) {
  35.         cout << (b2 - b1) / a1 << " 0";
  36.         return 0;
  37.     }
  38.  
  39.     long long x0, y0;
  40.     long long g = extGCD(a1, a2, x0, y0);
  41.     long long diff = b2 - b1;
  42.     long long x = x0 * (diff / g);
  43.     long long step1 = a2 / g;
  44.     long long step2 = a1 / g;
  45.  
  46.     x =(x %step1 + step1) % step1;
  47.     long long x2 = (a1 * x + b1 - b2) / a2;
  48.  
  49.     if (x2 < 0) {
  50.         long long k = (-x2 + step2 - 1) / step2;
  51.         x += k * step1;
  52.         x2 += k * step2;
  53.     }
  54.  
  55.     cout << x <<" "<< x2;
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
517876754383 96879
https://ideone.com/cGhEW0
language:
C++14 (clang 8.0)
created:
15 hours ago
visibility:
public

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!