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之前，要先来认识一下这个定理。

引自：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。但由于这里要遍历，故我觉得还是要用map。unordered_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）

扩展欧几里得定理

引自：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;
}