W.01 辗转相除法
提示：本文主要偏于数学证明.
[定义] 整除：
\(a,b\in \mathbb{N}\)，若 \(\exists c\in \mathbb{N}\)， 使得 \(a=bc\)，称 \(b\) 整除 \(a\)，记作 \(b\mid a\).
[定义] 带余除法：
\(a,b\in \mathbb{N}\)，\(a>b\)，则 \(\exists k,r\in \mathbb{N}\)，使得 \(a=kb+r\) 且 \(r<a\)。称 \(r\) 是余数.
[定义]公因数：
\(a,b\in \mathbb{N}\)，若 \(c\) 有 \(c\mid a\) 且 \(c\mid b\)，称 \(c\) 是 \(a,b\) 的公因数.
[定义]最大公因数：
记全体 \(a,b\) 的公因数组成的集合为 \(S\)，其中最大元素 \(c\) 称为 \(a,b\) 的最大公因数，记作 \((a,b)=c\).
[定理]
\(a,b\in \mathbb{N}\)，\(a>b\)，\(a=kb+r\)为其带余除法。则 \((a,b)=(r,b)\).
证明：
首先证明 \(c=(a,b)\) 是 \(r,b\) 的公因数.
由 \(c=(a, b)\) 知 \(c\mid a\) 且 \(c\mid b\).
也即 \(\exists n, m\in \mathbb{N}\)，使得 \(a=nc\)，\(b=mc\).
代入带余除法式子，\(nc=kmc+r\).
故 \(r=nc-kmc=(n-km)c\)，推出 \(c\mid r\).
又由 \(c\mid b\) 知 \(c\) 是 \(r,b\) 的公因数.
然后证明 \(c\) 是 \(r,b\) 最大的公因数. 使用反证法：
若 \(\exists d>c\)，\(d\mid r\) 且 \(d\mid b\).
有 \(\exists p, q\in \mathbb{N}\)，使得 \(r=pd, b=qd\).
代入带余除法式子，\(a=kqd+pd=(kq+p)d\).
得到 \(d\mid a\).
又有 \(d\mid b\)，故 \(d\) 是 \(a,b\) 的公因数.
由 \(c\) 是最大公因数知 \(d\leqslant c\)，这与假设矛盾.
故 \((a,b)=(r,b)\). 得证.
[辗转相除法]（下文 % 记号是 C++ 中运算符）
通过上面的定理，我们可以将求 \((a,b)\) 中一者降小，重复操作即可.
不妨看两个例子：
\((15,6)=(15\%6,6)=(3,6)=(3,6\%3)=(3,0)=3\).
\((8,5)=(8\%5,5)=(3,5)=(3,5\%3)=(3,2)=(3\%2,2)=(1,2)=(1,2\%1)=(1,0)=1.\)
可以看出带余除法是互相之间一直在辗转的，直到某一项为 \(0\) 为止.
[代码实现]
#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
if(a<b)swap(a,b);
while(b!=0){
a=a%b;
swap(a,b);
}
cout<<a;
}
说明：每次让 a>b 是为了不讨论该谁去除谁得到余数的问题。
swap(a,b) 是一个操作（函数），能够交换 a,b 的值。
你可以用中间变量实现它，不过这样写更方便。