数论-- 欧几里得算法，扩展欧几里得算法

欧几里得算法(gcd)

就是辗转相除法

作用：求gcd(a,b)

公式：

[gcd(a,b) = gcd(b,a\%b) ]

写法1：

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

写法2 :位运算(超快) (a,b不能为0)

int gcd(int a , int b){
	while(b ^= a ^= b ^= a %= b);
	return a;
}

详解看这里

扩展欧几里得算法(exgcd)

用途：1.求二元一次方程的特解，通解 2.求乘法逆元

裴蜀定理：

对于任意正整数 (a) , (b) ，一定存在整数 (x) , (y) ,使得

[ax+by == gcd(a,b) ]

且对于任意 (x) ,(y)， (ax+by) 一定是d的倍数 [d为gcd(a,b)]

扩展欧几里得算法的作用：

exgcd提供了一种算法，对于任意(a,b)，都能求出 (ax+by=d) 的解 (x,y)
顺便还能求出gcd

int exgcd( int a , int b , int &x , int &y ){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int ans = exgcd( b , a % b , x , y );
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return ans;
}

解释：
讲的很清晰

通解：待补