欧几里得算法
辗转相除法求最大公约数
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}
裴蜀定理
裴蜀定理:对于任意两个整数a、b，设 d=gcd(a,b) 为它们的最大公约数，那么一定存在整数 x 和 y，使得 ax+by=d 成立。并且，形如 ax+by（x,y∈Z）的所有整数都是 d 的倍数，反之，d 的任意倍数也都可以表示成 ax+by 的形式。
特别地，a 和 b 互质（即 gcd(a,b)=1）的充分必要条件是存在整数 x 和 y，使得 ax+by=1。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
