前置知识

斐蜀定理（贝祖定理）

写在前面

鸣谢：扩展欧几里得算法——exgcd

Q：啥叫扩展欧几里得啊

A：扩展欧几里得算法是用来在已知 \(a, b\) 求解一组 \(x, y\) ，使他们满足斐蜀等式： \(ax + by = \gcd(a, b) = d\)

尝试搞一下它

先考虑一下比较简单的特殊情况，如果 \(b = 0\)，那么 \(\gcd(a, b) = a\)，并显然存在一组解 \(x = 1, y = 0\)

对于一般情况，设 \(ax + by = \gcd(a, b)\)，

根据欧几里得算法， \(\gcd(a, b) = \gcd(b, a \bmod b)\)

肯定存在式子 \(bx_2 + (a \bmod b)y_2 = \gcd(b, a \bmod b)\)

\[\therefore ax_1 + by_1 = bx_2 + (a \!\!\mod b)y_2 \]

\[\begin{alignedat}{3} \because ax_1 + by_1 & = bx_2 + (a - a \div b \times b)y_2 \\ & = bx_2 + ay_2 - a \div b \times b \times y_2 \\ & = ay_2 + b(x_2 - a \div b \times y_2) \end{alignedat}\]

\[\therefore x_1 = y_2 , y_1 = x_2 - a \div b \times y_2 \]

继续递推下去就好啦~

实现代码：

int exgcd(int a, int b, long long &x, long long &y)
{
    if(b == 0) return x = 1, y = 0, a;
    int d = exgcd(b, a % b, y, x);//d的值实际上就是gcd(a,b)，如果不需要的话可以不求
    return y -= a / b * x, d;
}

不过毕竟有扩欧这种帅气的名字，可不能只干这点活

它还可以求逆元：

设 \(x\) 为 \(a\) 在模 \(p\) 意义下的逆元，那么满足式子：

\[a \equiv 1 \]

那么有：

\[ax + my = 1 \]

然后用 \(exgcd\) 搞出 \(x\) 即可（这就是为啥 \(a\) 和 \(m\) 一定要互质才能使得 \(a\) 在模 \(m\) 意义下有逆元）

实现代码：

long long inv(long long a,long long m)
{
    long long x,y;
    long long d = exgcd(a, m, x, y);
    return d == 1 ? (x + m) % m : -1 ;//不互质就没有逆元
}

\(The\) \(end.\)