主页
Featured image of post ACM学习笔记——GCD、裴蜀定理、EXGCD……

ACM学习笔记——GCD、裴蜀定理、EXGCD……

数论——GCD、裴蜀定理、EXGCD……

文章字数:3321
预计阅读时长: 分钟

该笔记目前直接复制的之前的笔记,还未调整格式。页面格式、内容、链接等可能存在混乱错误……

GCD

引例:最大公约数

没什么好说的,就最大公约数。
主要是他的求解方法:欧几里得算法(Euclidean algorithm)(即:辗转相除法)。

欧几里得算法

也不多讲,证明也懒得_(:з」∠)_……
主要是他的扩展:**扩展欧几里得定理**(Extended Euclidean algorithm, EXGCD)【没有在套娃xddd……

主要依靠式子:$\gcd(a,b)=\gcd(b,a\mod b)$
当 $b=0$ 时,此时算出来的 $a$ 即为最终 $\gcd(a,b)$ 的结果。

时间复杂度为$O(\log n)$。

实现代码

  • 递归实现:
long long gcd(long long a, long long b)
{
	//if (a < b)
	//	return gcd(b, a);
	/* 删除原因:
	虽然用辗转相除法需要满足a > b。
	但如果a < b,则b % a = a,
	gcd(b, b % a)实际上就相当于交换了a,b。故不用单独判断。
	*/
	if (b == 0)
		return a;
	return gcd(b, b % a);
	/* 一行代码:
	return b ? gcd(b,b%a)
	*/
}
  • 迭代实现:
long long gcd_iteration(long long a, long long b)
{
    while (b ^= a ^= b ^= a %= b);	//b^=a^=b^=a为交换两变量操作,最后以b的值为循环条件。
    return a;
}

多个数的最大公约数

求 $a_1,a_2,\cdots,a_n$ 个数的最大公约数,
直接为 $\gcd(a_1,a_2,\cdots,a_n)$。

先算$\gcd(a_1,a_2)$,所得结果$d_1$,再$\gcd(d,a_3)$,反复进行。

此处以上为基础部分。


裴蜀定理(贝祖定理)

在学EXGCD之前,要先来认识一下这个定理。

裴蜀定理,又称贝祖定理(Bézout’s lemma)。是一个关于最大公约数的定理。

引自:OI-Wiki

定义

若 $a,b$ 是不全为零的整数,记:$\gcd(a,b)=d$,
则对于任意的整数 $x,y$ , $ax+by$ 都一定是 $d$ 的整数倍。

  • 特别的:一定存在整数 $x,y$ ,使 $ax+by=d$ 成立。
  • 为充要条件,即:
    若 $ax+by=c$ 有解,
    则 $\gcd(a,b)\mid c$ 。(其中 $\mid$ 为整除符号,代表$c$能被$\gcd(a,b)$整除)
    (或者说 $c$ 是 $\gcd(a,b)$的整数倍)

    • 特别的:如果 $ax+by=1$ ,则 $a,b$ 互质($\gcd(a,b)=1$)。

    这个即为二元一次不定方程存在解的条件。

简洁一点则为:

若 $a,b$ 是不全为零的整数,
则存在整数 $x,y$ , 使得 $ax+by=\gcd(a,b)$ 。

这个定理只是个概念,让你知道有这样的解存在,但并没有实际告诉你该怎么解。

推论

  1. 有关互质

    $a,b$ 互质($\gcd(a,b)=1$)的充要条件为:
    存在整数 $x,y$ ,使得$ab+by=1$

  2. 推广到$n$个数的情况:

    设存在$n$个整数 $a_1,a_2,\cdots,a_n$ , $d= \gcd(a_1,a_2,\cdots,a_n)$ ,
    则存在整数 $x_1,x_2,\cdots,x_n$ , $x_1a_1+x_2a_2+\cdots+x_na_n=d$ 有解。

    • 特别的:
      如果 $a_1,a_2,\cdots,a_n$ 互质,(不是两两互质,而是存在两个数互质,即:$\gcd(a_1,a_2,\cdots,a_n)=1$)
      则存在整数 $x_1,x_2,\cdots,x_n$ ,使得 $x_1a_1+x_2a_2+\cdots+x_na_n=1$ 。

参考自:“静听风吟。”的「数学:裴蜀定理」

基本应用(例题)

例题:Codeforces Round #290 (Div. 2) D. Fox And Jumping
给出$n$张卡片,分别有$l_i$和$c_i$。在一条无限长的纸带上,你可以选择花$c_i$的钱来购买卡片$i$,从此以后可以向左或向右跳$l_i$个单位。 问你至少花多少元钱才能够跳到纸带上全部位置。若不行,输出$-1$。

分析该问题:
如果每个格子都想要被跳到,则必须选出一些数,使得数次加减后绝对值为$1$。【我们定加减后值就为$1$。因为如果为$-1$,可以通过反向跳跃(取相反数)使得值为$1$。】
这样通过每次移动$1$格,便能满足跳到每个格子上,否则一定不能满足。

由上述裴蜀定理的“推论2”可知:
如果要满足 $x_1a_1+x_2a_2+\cdots+x_n*a_n=1$ ,
则必须满足 $\gcd(a_1,a_2,\cdots,a_n)=1$ 。

但又由于有代价的存在,【分析了这么多,那么代价呢x……
所以可以用$dp$思想:

用个dp表存跳某步的代价最小值。

那么每读入一个,则对所存的状态进行遍历,
求取其与某状态的$\gcd$,算出来是多少,则这两个数可以通过数次加减后走多少格

不断更新,最后如果dp[1]存在,则输出,否则输出-1

又因为数据范围太大,故用map来代替基本的数组来存。
【OI-Wiki上说可以用unordered_map。但由于这里要遍历,故我觉得还是要用mapunordered_map由于其内部是用哈希表实现的,遍历时可能访问不全。

部分代码

map<int, int> dp;
for (int i = 1; i <= n; i++)
{
    dp[l[i]] = dp[l[i]] ? min(dp[l[i]], c[i]) : c[i];	//如果存在要去最小
    for (auto j : dp)	//遍历当前dp表
    {
        int to = __gcd(l[i], j.first);	//计算能去的点(gcd)
        int cost = dp[l[i]] + j.second;	//计算代价
        dp[to] = dp[to] ? min(dp[to], cost) : cost;
    }
}

参考自:“Kanoon”的Codeforces Round #290 (Div. 2) D. Fox And Jumping(数论,裴蜀定理,gcd)

扩展欧几里得定理

扩展欧几里得定理(Extended Euclidean algorithm, EXGCD),常用于求 $ax+by= \gcd(a,b)$ 的一组可行解。

引自:OI-Wiki

方法详解

求 $ax+by= \gcd(a,b)$ 的一组可行解:

设:$a>b$,则有以下两种情况

  1. 当$b=0$时,$\gcd(a,b) = a$,所以存在一组解$\left{\begin{array}{ll}x = 1\y =0\end{array}\right.$

  2. 当$a=0$时,$\gcd(a,b)=\gcd(b,0)$,一样的结果。

  3. 当$ab\neq0$时:

    设:
    $\left{\begin{array}{ll} ax_1+by_1=\gcd(a,b) \ bx_2+(a \mod b)y_2=\gcd(b,a \mod b) \end{array}\right.$

    由欧几里得算法可知: $\gcd(a,b) = \gcd(b,a \mod b)$
    故: $ax_1+by_1 = bx_2+(a \mod b)y_2$

    又因为: $a \mod b = a-(\lfloor \frac{a}{b} \rfloor \times b)$
    所以:
    $ax_1+by_1$
    $= bx_2+[a-(\lfloor \frac{a}{b} \rfloor \times b)]y_2$
    $= ay_2+bx_2 - \lfloor \frac{a}{b} \rfloor \times by_2$
    $= ay_2+b(x_2 - \lfloor \frac{a}{b} \rfloor \times y_2)$

    因为上下两式中: $a=a,b=b$
    所以:$\left{\begin{array}{ll} x_1=y_2 \ y_1=x_2-\lfloor \frac{a}{b} \rfloor \times y_2 \end{array}\right.$

    便可得到递归式:$\textup{exgcd}(x,y)=\textup{exgcd}(y,x-\lfloor \frac{a}{b} \rfloor \times y)$(此时的$a,b$是属于$\textup{exgcd}(x,y)$状态的$a,b$)
    终止条件: $b=0$时,$\left{\begin{array}{ll}x = 1\y =0\end{array}\right.$

    虽然$\gcd(a,b)$和$\textup{exgcd}(a,b)$都有递归式,
    但$\textup{exgcd}$不同于求$\gcd$:

    • 求解$\gcd$是知道最开始的初状态,一直递归求得末状态
    • 求解$\textup{exgcd}$只是知道末状态,要根据末状态再倒推回去求解初状态(一组解)
      则需要不断递归到末状态,再由末状态反推到初状态。故可配合$\gcd$求得$\textup{ecgcd}$

实现代码

  • 递归实现:
//函数返回值为gcd,过程中计算x,y。
int Exgcd(int a, int b, int &x, int &y)
{
    if (b == 0) //代表通过gcd求得末状态,
    {
        x = 1, y = 0; //由上分析知:终状态为x = 1, y = 0。
        return a;
    }
    int gcd = Exgcd(b, a % b, x, y); //直接递归gcd求
    int t = x;                       //这里之后开始反推回去
    x = y;
    y = t - (a / b) * y;
    return gcd;
}
  • 迭代实现:

    有关$\textup{exgcd}$的迭代方式,可以采用矩阵乘法的思路理解。

    这是我们找到的递归式:
    $$\textup{exgcd}(x,y)=\textup{exgcd}(y,x-\lfloor \frac{a}{b} \rfloor \times y)$$
    或写为:$\left{\begin{array}{ll} x=y' \ y=x'- \lfloor \frac{a}{b} \rfloor \times y' \end{array}\right.$(此时的$a,b$是属于$\textup{exgcd}(x,y)$状态下的$a,b$)

    变成矩阵形式: $$\begin{pmatrix} x \ y \end{pmatrix}=\begin{pmatrix} 0&1 \ 1&-d_1 \end{pmatrix}\begin{pmatrix} x' \ y' \end{pmatrix}$$ 其中$d_1$表示第一次迭代(初状态)的$\lfloor\frac{a}{b}\rfloor$。

    然后就可以一直乘下去展开,直到最终状态: $$\begin{pmatrix} x \ y \end{pmatrix} = \begin{pmatrix} 0&1 \ 1&-d_1 \end{pmatrix} \begin{pmatrix} 0&1 \ 1&-d_2 \end{pmatrix} \cdots \begin{pmatrix} 0&1 \ 1&-d_n \end{pmatrix} \begin{pmatrix} 1 \ 0 \end{pmatrix}$$ 因此就可以顺着迭代:计算出中间$n$个二阶矩阵$\begin{pmatrix} 0&1 \ 1&-d_i \end{pmatrix}$的乘积。最后到最终状态乘$\begin{pmatrix} 1 \ 0 \end{pmatrix}$,也就是直接取最终算出的二阶矩阵$\begin{pmatrix} x_1&x_2 \ y_1&y_2 \end{pmatrix}$的$x_1,x_2$


    我们还可以调整一下,设定一个初矩阵,然后直接乘每次的$\begin{pmatrix} 0&1 \ 1&-d_i \end{pmatrix}$,就不用额外处理初状态,直接顺着迭代着走就可以了。
    否则需要额外处理初状态,要令初矩阵为$\begin{pmatrix} 0&1 \ 1&-d_1 \end{pmatrix}$,然后还要迭代次$\gcd(a,b)$才能进入循环。
    易知这个初状态就是单位矩阵$\begin{pmatrix} 1&0 \ 0&1 \end{pmatrix}$。

int Exgcd(int a, int b, int &x, int &y)
{
    x = 1, y = 0;           //初矩阵:1 0
    int x1 = 0, y1 = 1;     //       0 1
    /* 不定义这个初矩阵的话就要写为:
    x = 0, y = 1;           //初矩阵:0  1
    int x1 = 1, y1 = -a/b;  //       1 -d1
    tie(a, b) = make_tuple(b, a - (a/b) * b);   //然后还要迭代一下
    */
    while (b)
    {
        int d = a / b;
        tie(x, x1) = make_tuple(x1, x - d * x1);    //矩阵乘法
        tie(y, y1) = make_tuple(y1, y - d * y1);
        tie(a, b) = make_tuple(b, a - d * b);       //迭代gcd()
    }
    return a;
}