GCD

Leetcode上的780.到达终点, 是gcd(最大公约数)的变种, 没看出, 深入了解了一下, 发现我根本不懂gcd, 因此来学一学

gcd(最大公约数)

先从求gcd开始

暴力

暴力法咯, 这还用多说, 写就完事儿

int gcd(int a, int b)
{
    if(a < b)
        swap(a, b);
    int res = 1;
    for(int i = 2; i < b/ 2; ++i)
        if(a % i == 0 && b % i == 0)
            res = i;
    return res;
}

辗转相除法(欧几里得算法)

原理如下: $gcd(a, b) = gcd(b, a \% b); (a > b \And a \% b\neq 0)$

证明? 我就不为难自己了

// 迭代
int gcd(int a, int b)
{
    if(a < b)
        swap(a, b);
    int temp;
    while(b)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
// 递归
int gcd(int a, int b)
{
    return b > 0 ? gcd(b, a % b) : a;
}

更相减损术

原理: $gcd(a,b) = gcd(a-b,c); (a>b)$

// 迭代
int gcd(int a, int b)
{
    while(a != b)
    {
        if(a > b)
            a -= b;
        else
            b -= a;
    }
    return a;
}
// 递归
int gcd(int a, int b)
{
    return a == b ? a : (a > b ? gcd(a - b, b) : gcd(a, b - a));
}

性能分析: 辗转相除会在两个数较大时在取模运算中性能下降, 然而, 若两者差较大, 更相减损术时间复杂度会退化至$O(n)$, 辗转相除法稳定于$O(\log{n})$

更深入一点可以借用斐波那契数列对辗转相除法取模次数进行分析, 从而进一步分析其最差时间复杂度, 然而我顶不住, 这篇博客有数学证明

Stein算法

更相减损术的改进版, 通过除法减少迭代次数

// 迭代
int gcd(int a, int b)
{
    int multiply = 1;
    while(a != b)
    {
        if(a & 1 == 0 && b & 1 == 0)
        {
            multiply *= 2;
            a /= 2;
            b /= 2;
        }
        else if(a & 1 == 0)
            a /= 2;
        else if(b & 1 == 0)
            b /= 2;
        else
        {
            if(a > b)
                a -= b;
            else
                b -= a;
        }
    }
    return a * multiply;
}
// 递归
int gcd(int a, int b)
{
    if(a == b)
        return a;
    if(a < b)
        gcd(b, a);
    else
    {
        if(a & 1 == 0 && b & 1 == 0)
            // 一些没必要的写法(相信现代编译器)
            // gcd(a >> 1, b >> 1) << 1;
            return 2 * gcd(a / 2, b / 2);
        else if(a & 1 == 0)
            return gcd(a / 2, b);
        else if(b & 1 == 0)
            return gcd(a, b / 2);
        else
            return gcd(a - b, b);
    }
}

780.到达终点

其中的快速逼近策略类似于辗转相除, 可以相互借鉴, 但是题目本身以及题解和求gcd是没关系的, 原题解

逆向思维还是很好想到的, 直接从起点出发路径选择太多, 而从终点出发路径是唯一的(大减小)

进一步来说, 我们一直用大的减小的如果到达起点返回true, 否则false. 这种线性探测会超时, 因此要将多次相减合并. 若我们合并了$k$次操作, 那么有 $tx-k\times ty=m \Rightarrow tx=m+k\times ty$, 最终剩下的余数则是我们快速逼近的结果

Accepted
195/195 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 50.33 % of cpp submissions (5.8 MB)

class Solution
{
public:
    bool reachingPoints(int sx, int sy, int tx, int ty)
    {
        while (tx > sx && ty > sy)
            if (tx < ty)
                ty %= tx;
            else
                tx %= ty;
        // 越界则不可达
        if (tx < sx || ty < sy)
            return false;
        // 那边达到了, 固定一边检查另一边
        return tx == sx ? (ty - sy) % tx == 0 : (tx - sx) % ty == 0;
    }
};