上午

关键词：数论，线性筛素数，扩展欧几里得

好蒙蔽啊！

最大公因数

使用辗转相除法求解，原理是$$gcd(a,b)=gcd(b,a \% b)$$

代码

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a; 
}

扩展欧几里得

斐蜀定理：对于不完全为$0$的非负整数$a,b$，$gcd(a,b)$表示$a,b$的最大公约数，必然存在整数对$(x,y)$，使得$gcd(a,b)=ax+by$。如：$5x+3y=1$。

怎么求这个特解$(x,y)$呢？我们注意到：欧几里德算法停止的状态是：$a=gcd(a,b)，b=0$，即当$x=1,y=0$时，这是最终状态。

代码

int egcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    int e = egcd(b, a%b, x, y);
    int t = x;x = y;y = t - a / b * y;
    return e;
}

这段代码的返回值是$gcd(a,b)$，x存储特解$x_0$，y存储特解$y_0$。

下午

下午断网了。

晚上

晚上网好了。

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/284.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。