上午

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

好蒙蔽啊！

最大公因数

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

代码

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

扩展欧几里得

怎么求这个特解$(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$。

下午

下午断网了。

晚上

晚上网好了。