ABC340-F S=1

今天补一道ABC340的F，学习一下Extented Euclidean（扩展欧几里得）定理

原题链接： F - S=1

为了解决不定方程 ax + by = gcd(a,b)，可以通过辗转相除法得到，代码如下，代码的返回值即为方程 ax + by = gcd(a,b) 的一个特解。

具体的数学证明可见：知乎-（扩展）欧几里得算法

pair<long long, long long> extgcd(long long a, long long b) {
  if (b == 0) return make_pair(1, 0);
  long long x, y;
  tie(y, x) = extgcd(b, a % b);
  y -= a / b * x;
  return make_pair(x, y);
}