题解-1003-更相减损术

解题思路

更相减损术的百度百科如下，更替相减的操作是重复且有尽头的，即本质可递归实现：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用 $2$ 约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个 $2$ 的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。
解释一下第二步：就是每次都用较大的数减去较小的数，这时候得到的差值去和较小的数比较，相等即终止，不等就继续（差值和较小的数）执行较大的数减较小的数的操作。
因此写递归函数的时候固定了 $a$ 和 $b$ 的含义， $a$ 始终存较大的数， $b$ 始终存较小的数，可稍微简化一下代码，最后将第一步中除去的 $2$ 简约复原（ $t i m e 2$ 次）的操作用前面题解用过的移位来进行，因为这里给出的两个数的数据范围在 $i n t$ 以内，因此直接用
$1 < < t i m e 2$ 即可完成。

通过代码

#include<bits/stdc++.h>
using namespace std;
int dg(int a,int b)
{
    int tmp = a + b;
    if (a == b)  return a;
    if (a < b)
    {
        a = b;
        b = tmp - a;
    }
    a -= b;
    return dg(a, b);
}
int cal(int a, int b)
{
    int time2 = 0, k = 0;
    while (a % 2 == 0 && b % 2 == 0)
    {
        a /= 2;
        b /= 2;
        time2++;
    }
    return (1 << time2)*dg(a,b);
}
int main()
{
    int a, b;
    cin >> a >> b;
    cout << cal(a,b) << endl;
    return 0;
}