扩展欧几里得算法//gcd(最大公约数)函数//lcm(最小公倍数)函数

扩展欧几里得算法：

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）= ax+by。

对于式子ax+by=m来说，我们并不仅仅想要知道有没有解，而是想要知道在有解的情况下这个解到底是多少。

所以，扩展欧几里得

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b){
    x = 1; y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a/b) * x;return d;
}

gcd函数

原理：辗转相除法

递归算法

当余数为0的时候，最后的a即为最大公约数。
先用较小的数对较大的数取余，再用余数对较小的数求余，直到余数为零 。

int gcd( int a , int b )
{
    return b == 0 ? a : gcd( b , a%b ) ;	
}

位运算

int gcd( int x , int y )
{
    while( y ^= x ^= y ^= x %= y ) ;return x ;
}

PS： ^ 是异或，x ^ x = 0 ， x ^ 0 = x 。 等号从右往左结合 。
1 ^ 1 = 0 ，1 ^ 0 = 1 ， 0 ^ 1 = 1 ，0 ^ 0 = 0 。

//使用异或运算交换两个数值
void swap( int &a , int &b ) 
{
    a=a^b;b=a^b;a=a^b;
}

LCM函数

ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a%b);
}ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}