博客

先上代码

int main()
{	
	int m, n, r;
	cin >> m >> n;
	while (n) {
		r = m % n;
		m = n;
		n = r;
	}
	cout << m;
}

对于m = k*n + r来说（m > n），gcd算法依靠的是m，n的公约数数集合和n，r的公约数集合相同，故在r不断减小下，r最终会变为最大公约数此时的余数为0。

证：设m，n的公约数集合为F，设n，r的为G。此时g（属于G）一定能整除m，所以有G<=F。将

m=k*n+r

变形为

m-k*n=r

，有f（属于F）一定能整除r，故F<=G。则得证F==G。

如果r比最大公约数大，是会不断缩小的，又每次必定会缩小至少1，对于有限数，则一定会缩小到最大公约数（必须满足公约数集合相同，r不会缩小到比最大公约数小不然矛盾）。

时间复杂度为O(logM)

因为M % N <= M/2，N如果<=M/2自不必说，N如果大于M/2那么M中只有一个N余数也小于M/2。所以复杂度为2*logM（应为要计算两次第一次的r才会移动到M的位置）。