exgcd
exgcd
理解
函数的返回值仍然是gcd，整个函数的过程是先向下递归算gcd，回溯的时候把不定方程求解出来了
代码
#include <bits/stdc++.h>
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
return x = 1, y = 0, a;
}
int r = exgcd(b, a % b, x, y);
std::tie(x, y) = std::make_tuple(y, x - (a / b) * y);
return r;
}
全志科技工作强度 17人发布
投递字节跳动等公司9个岗位
