exgcd

发表于 分类于 ， 阅读次数： 本文字数： 153 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
// a * x + b * y = gcd(a, b) 的一组特解
pll exgcd(i64 a, i64 b) {
  if (!b)
    return {1, 0};
  pll res = exgcd(b, a % b);
  return {res.se, res.fi - a / b * res.se};
}