成都外国语学校信息学夏令营 Day10

上午

关键词:数论,线性筛素数,扩展欧几里得

好蒙蔽啊!

最大公因数

使用辗转相除法求解,原理是$$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$。

下午

下午断网了。

晚上

晚上网好了。

Last modification:June 29th, 2019 at 06:49 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment