原理如下：
1、更相减损术
以112和84为例，为什么gcd(112,84)=gcd(112-84,84)？？（gcd表示最大公因数）。
为了方便我把gcd(112,84)记为x，那么112必然是x的整数倍，84也必然是x的整数倍，x的整数倍减去x的整数倍等于什么？还是x的整数倍啊！所以相减完的数任然有x这个因数，即gcd(112-84,84)=x=gcd(112,84)。
代入数据，gcd(112,84)=28，112=4*28，84=3*28，112-84=28=1*28，显然一倍的28和3倍的28的最大公因式还是28。
2、辗转相除法其实就是更相减损术的反复应用。
假如现在我给你两个数1204和84，让你求gcd(1204,84)。如果你用更相减损术，那么你的运算过程是这样的：gcd(1204,84)=g(1204-84,84)=gcd(1204-84-84,84)=...你发现了什么？你发现进行了很多次减法！我们可以用乘法代替！
gcd(1204,84)=gcd(1204-n*84,84)，n是减去的84的个数。我们如何一步到位找到最大的n呢？也就是说1204最多能被84减多少次呢？也就是说1204大概是84的多少倍呢？
你发现，带余除法可以一步到位算出n：
1204÷84=14……28，也就是说1204最多能减14个84，减完剩下28。这个28就是我们想要的，gcd(1204,84)=gcd(1204-14*84,84)=gcd(28,84)。
实际上我们只需要除完的余数，得到余数的运算叫做模运算，C++中用%表示，1204%84=28。这就是辗转相除法。
温馨提示：答案为网友推荐，仅供参考
相似回答