fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast ios::sync_with_stdio(false); cin.tie(nullptr);
  5. #define ll long long
  6. #define endl '\n'
  7. #define all(v) (v).begin(), (v).end()
  8. #define rall(v) (v).rbegin(), (v).rend()
  9.  
  10. const int oo = 1e9;
  11. const ll INF = 1e18;
  12.  
  13. ll gcd(ll a, ll b, ll& x, ll& y) {
  14.     if (b == 0) {
  15.         x = 1;
  16.         y = 0;
  17.         return a;
  18.     }
  19.  
  20.     ll x1, y1;
  21.     ll d = gcd(b, a % b, x1, y1);
  22.  
  23.     x = y1;
  24.     y = x1 - y1 * (a / b);
  25.  
  26.     return d;
  27. }
  28.  
  29. bool find_any_solution(ll a, ll b, ll c, ll& x0, ll& y0, ll& g) {
  30.     g = gcd(abs(a), abs(b), x0, y0);
  31.  
  32.     if (c % g)
  33.         return false;
  34.  
  35.     x0 *= c / g;
  36.     y0 *= c / g;
  37.  
  38.     if (a < 0)
  39.         x0 = -x0;
  40.  
  41.     if (b < 0)
  42.         y0 = -y0;
  43.  
  44.     return true;
  45. }
  46.  
  47. void solve() {
  48.     ll n, k;
  49.     cin >> n >> k;
  50.  
  51.     ll a = n / k;
  52.     ll b = (n + k - 1) / k;
  53.     ll x, y, g;
  54.     find_any_solution(a, b, n, x, y, g);
  55.     cout << x << " " << y << endl;
  56. }
  57.  
  58. int main() {
  59.     fast
  60.  
  61.     int t = 1;
  62.     cin >> t;
  63.  
  64.     while (t--)
  65.         solve();
  66.  
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1
https://ideone.com/ktu6Xa
language:
C++ (gcc 8.3)
created:
2 days 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!