fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // make sure modify 0LL + , 1LL * , overflow when remove define
  6. #define int long long
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. int extended_gcd(int a, int b, int& x, int& y) {
  10.     if (a < 0) {
  11.         int g = extended_gcd(-a, b, x, y);
  12.         x *= -1;
  13.         return g;
  14.     }
  15.     if (b < 0) {
  16.         int g = extended_gcd(a, -b, x, y);
  17.         y *= -1;
  18.         return g;
  19.     }
  20.     if (b == 0) {
  21.         x = 1, y = 0;
  22.         return a;
  23.     }
  24.     int g = extended_gcd(b, a % b, y, x);
  25.     y -= (a / b) * x;
  26.     return g;
  27. }
  28.  
  29. void shift(int& x, int& y, int a, int b, int t) {
  30.     x += t * b, y -= t * a;
  31. }
  32.  
  33. bool solve(int a, int b, int c, int minx, int miny, int& x, int& y, int& g) {
  34.     g = extended_gcd(a, b, x, y);
  35.     if (c % g != 0) return false;
  36.  
  37.     x *= c / g, y *= c / g, a /= g, b /= g;
  38.  
  39.     int fa = ( (a > 0) ? (1) : (-1) );
  40.     int fb = ( (b > 0) ? (1) : (-1) );
  41.  
  42.     shift(x, y, a, b, (minx - x) / b);
  43.     if (x < minx) shift(x, y, a, b, fb);
  44.     int save = x;
  45.  
  46.     shift(x, y, a, b, -(miny - y) / a);
  47.     if (y < miny) shift(x, y, a, b, -fa);
  48.     x = max(x, save);
  49.  
  50.     return true;
  51. }
  52.  
  53. void get_shit_done() {
  54.     int n, m, a, k;
  55.     while (cin >> n >> m >> a >> k) {
  56.         if (n + m + a + k == 0) return;
  57.         int x, y, g;
  58.         if ( solve(a, -m, n - k, 1, 0, x, y, g) ) {
  59.             cout << x * a + k << '\n';
  60.         } else {
  61.             cout << "Impossible\n";
  62.         }
  63.     }
  64. }
  65.  
  66. signed main() {
  67.     _3bkarm
  68.  
  69.     int ts = 1;
  70. //    cin >> ts;
  71.     while (ts--) {
  72.         get_shit_done();
  73.     }
  74.  
  75.     return 0;
  76. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NQQL1V
language:
C++14 (clang 8.0)
created:
1 day 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!