Cacher is the code snippet organizer for pro developers

LL gcd(LL a, LL b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

LL lcm(LL a, LL b) {
  if ((a == 0) || (b == 0)) return 0LL;
  return ((a / gcd(a, b)) * b);
}

args: a, b, x, y

• a, b: gcd input
• x, y: (x, y) s.t. ax + by = gcd(a, b)
• return value: gcd(a, b)

LL ext_gcd(LL a, LL b, LL *x, LL *y) {
  if (b == 0) {
    *x = 1;
    *y = 0;
    return a;
  }
  LL v = ext_gcd(b, a%b, y, x);
  (*y) -= a/b * (*x);
  return v;
}

// Kx - Ny = -S
// -> return x
void solve() { 
  LL N, S, K; cin >> N >> S >> K;
  LL x, y;
  LL v = ext_gcd(K, -N, &x, &y);
  if (S % v == 0) {
    S /= v;
    N /= v; 
    x *= -S;
    x %= N;
    if (x < 0) x += N;
    cout << x << endl;
  } else {  
    cout << -1 << endl;
  }
}