欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
int gcd(int x, int y){ if(y == 0) return x; return gcd(y, x % y); }用最大公约数求最小公倍数
printf("%d\n", x / gcd(x, y) * y);扩展：直接交换两个值的方法
#include<stdio.h> int main(int argc, char const *argv[]){ int a, b; cin >> a >> b; a ^= b ^= a ^= b; cout << a << b; }扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
贝祖定理：贝祖定理是代数几何中一个定理，其内容是若设a,b是整数，则存在整数x,y，使得ax+by=gcd（a,b），(a,b)代表最大公因数，则设a,b是不全为零的整数，则存在整数x,y，使得ax+by=(a，b)
因子
a|b表示a是b的因子，b是a的倍数
不定方程有整数解
ax+by = c有整数解，当且仅当gcd(a, b)|c
求解一般线性方程
定理：若ax + by = g, (g = gcd(a, b), 即g是a，b的最大公约数) 有整数解(x1, y1)； 则ax + by = c(c是g的倍数）有整数解（cx1/g, cy1/g）
求解乘法逆元
x = a % b = a - a / b * b
a * _a mod m == 1则称_a为a关于模m的乘法逆元，它等价除法
a / b % m = a * _b % m
(a * _a) % m = 1等价于 a * x + m * y = 1,之后利用扩展欧几里德算法求解x0
最小正整数逆元就为x = （x0 % m + m） % m
当m为负时，m = -m即可
只有两个数互素的时候才会有乘法逆元
两个数不互素是没有乘法逆元的
eg：HDU 1576(A/B)
1、n=A%9973，则n=A-A/9973*9973。又A/B=x，则A=Bx。所以Bx-A/9973*9973=n。即Bx-9973y=n。
到这里我们可以发现：只要求出x的值，即可算出x%9973，也就是(A/B)%9973了。顺利解决了！
2、题目关键转到如何求出x了。题目的输入是n和B，利用扩展欧几里德算法可求出gcd(B,9973)=Bx1+9973y1=1的x1。
等式两边同乘以n，得B(nx1)-9973(-ny1)=n。可知nx1就是Bx-9973y=n的解了！！！即x=nx1。
3、对于第三部得到的x可能是负数，由题这显然是不正确的。
可以做这样的转化：(x%9973+9973)%9973
#include<stdio.h> #include<iostream> #include<memory.h> #define MOD 9973 using namespace std; int exgcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1; y = 0; return a; } int d = exgcd(b, a % b, x, y); int tmp = x; x = y; y = tmp - a / b * y; return d; } int main(int argc, char const *argv[]) { int t, n, B; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &B); int x, y; int d = exgcd(B, MOD, x, y); x *= n; printf("%d\n", (x % MOD + MOD) % MOD); } return 0; }
