exgcd

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    i64 gcd = exgcd(b, a % b, x, y);
    i64 tmp = x;
    x = y;
    y = tmp - a / b * y;
    return gcd;
}

i64 cal(i64 a, i64 b, i64 c) {
    i64 x, y;
  i64 gcd = exgcd(a, b, x, y);
  if (c % gcd != 0) return -1;
  x *= c / gcd;
  b /= gcd;
  i64 ansx = x % abs(b);
  if (ansx <= 0) ansx += b;
  return ansx;
}
// c 可以为负值！直接带入 -1 是没问题的！
// 调用cal即为解方程组 ax + by = c 的最小 x, 全部解为 x +- t * b / gcd(a, b); (t为任意整数)