乘法逆元（部分施工）、exgcd

求模意义下的乘法逆元

如果一个线性同余方程 \(ax\equiv1\pmod p\)，则 \(x\) 称为 \(a\bmod p\) 的逆元，记作 \(a^{-1}\)。

exgcd

直接解这个同余方程。（有关 exgcd，详见后文。）

\(ax\equiv 1 \pmod p\) 可以被改写为 \(ax + py = 1\)。显然其有整数解的充要条件为 \(a,p\) 互质。exgcd 后，\((x+p)\bmod p\) 就是结果。

费马小定理：快速幂

\(x \equiv a^{p-2} \pmod p \left(p \space \text{is a prime}\right)\)

由上得 \(ax \equiv a^{b-1} \pmod p\)（费马小定理，要求 p 是质数）；
所以 \(x \equiv a^{b-2} \pmod p\)。

\(O(n)\) 递推

\[i^{-1}= \begin{cases} 1 & i=1 \\ (p-\lfloor\frac{p}{i}\rfloor)+{(p\bmod i)}^{-1} & \text{otherwise.} \end{cases} \pmod p\]

证明：

\(i=1\) 时显然。

对于其他情况，我们可以对 \(p\) 进行带余除法，将其表示为 \(ai+b(b<i)\)。
即 \(b=p\bmod i,a = \lfloor\frac{p}{i}\rfloor\)。

移项后可得：\(-b\equiv ai\pmod p\)。

令两边同乘以 \(i^{-1}b^{-1}\)，继续推导：

\[\begin{aligned} -b\times i^{-1}\times b^{-1} &\equiv i^{-1}\times b^{-1}\times ai\pmod p\\ -i^{-1}&\equiv b^{-1}\times a\pmod p\\ i^{-1}&\equiv{(p\bmod i)}^{-1}\times-\lfloor\frac{p}{i}\rfloor\pmod p\\ i^{-1}&\equiv{(p\bmod i)}^{-1}\times\left(p-\lfloor\frac{p}{i}\rfloor\right)\pmod p \end{aligned} \]

得证。

exgcd

基础

常用于求 \(ax+by=\gcd(a,b)\) 的一组可行整数解。

设 \(\gcd(a,b)=d\)，则 \(ax+cy=d\)。

设有一组解 \(x_1,y_1\)，满足 \(bx_1+(a\bmod b)y_1=\gcd(b,a\bmod b)=d\)。所以 \(ax+by=bx_1+(a\bmod b)y_1\)。

又因为 \(a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)\)，所以 \(ax+by=bx_1+(a-\lfloor\frac{a}{b}\rfloor\times b)y_1\)。

推导：

\[ax+by = bx_1+ay_1-(\lfloor\frac{a}{b}\rfloor\times b)y_1 = ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor)y_1 \]

即 \(x=y_1,y=x_1-\lfloor\frac{a}{b}\rfloor y_1\)。

代码

注：显然当 \(a=1,b=0\) 时，方程的一组解为 \(x=1,y=0\)。以此作为递归终止条件。

void exgcd(ll a, ll b, ll &x, ll &y) {if(!b) { x = 1, y = 0; return ; }exgcd(b, a % b, y, x); // x=y_1,y->x_1y -= a / b * x; // y=x_1-a/b*y_1
}

板子。

应用 1：板子 2。困难起来了？

现在的任务是求 \(ax+by=c\) 的通解。（无解非常好判定，只要 \(c \mid \gcd(a,b)\) 不满足就无解）

求第一组解

还是设 \(d = \gcd(a,b)\)。

滤除了没有解的情况，我们就可以用 \(ax'+by'=d\) 来求 \(ax+by=c(c=kd,k\in\mathbb Z)\) 的整数解。

两边同乘 \(k\) 得：\(akx'+bky'=kd=c\)，所以 \(x=kx',y=ky'\) 就是这个方程的一组解了。

这里设 \(x_0=x'\times\frac{c}{d},y_0=y'\times\frac{c}{d}\)。

用 \(x_0,y_0\) 找出方程所有解

设 \(a(x_0+\Delta x)+b(y_0+\Delta y) = c(\Delta x,\Delta y\in\mathbb Z)\)

展开后可得：\(ax_0+by_0+a\Delta x+b\Delta y=c\)，即 \(a\Delta x+b\Delta y=0\)。

对这个方程，我们可以构造 \(\Delta x=t\times\frac{b}{d},\Delta y=-t\times\frac{a}{d}\)，这样方程左边就等于 \(\frac{ab}{d}-\frac{ab}{d}=0\) 了。

这样任取一个整数 \(t\)，就可以算出相应的 \(m,n\)，进而推出 \(x,y\)，得到通解。

解的最值

由上，\(x=x_0+t\times\frac{b}{d}, y=y_0-t\times\frac{a}{d}\)，且 \(x+y\) 一定。
又有 \(t\) 越大，\(x\) 越大，\(y\) 越小。

设 \(\frac{b}{d} = d_x, \frac{a}{d} = d_y\)。

因为 \(x,y>0\)，所以 \(x_0+t\times d_x>0, y_0-t\times d_y>0\)。

解得 \(\dfrac{-x_0}{d_x}<t<\dfrac{y_0}{d_y}\)。

因为 \(t\in\mathbb Z\)，所以 \(\lceil\cfrac{1-x_0}{d_x}\rceil\le t\le\lfloor\cfrac{y_0-1}{d_y}\rfloor\)。

若这个关系式无法被满足，那么显然不可能让 \(x,y\) 都是正整数；否则就有正整数解，正整数解个数即为 \(s\) 的合法整数取值个数。

而对于最大最小值，\(x\) 的最大值和 \(y\) 的最小值都是在 \(s\) 最大时取到，而 \(x\) 的最小值和 \(y\) 的最大值反之。

代码整合

using db = long double;
using ll = long long;void exgcd(ll &x, ll &y, ll a, ll b){if(! b){x = 1, y = 0;return ;}exgcd(y, x, b, a % b);y -= a / b * x;
}int main(){int T; cin >> T;while(T --){ll a, b, c, d;cin >> a >> b >> c;if(c % (d = __gcd(a, b))){cout << "-1\n"; // 无解continue;}ll x, y, xmax, ymax, xmin, ymin;exgcd(x, y, a, b); // 求 x'，y'x *= c / d, y *= c / d; // 求 x_0, y_0db dx = b / d, dy = a / d; // d_x,d_yll tmin = ceil(db(1-x) / dx), tmax = floor(db(y-1) / dy); // 求 t 的取值范围xmax = x + tmax * dx, ymin = y - tmax * dy;xmin = x + tmin * dx, ymax = y - tmin * dy;if(ymax <= 0 || xmax <= 0){ // 代入cout << xmin << ' ' << ymin << '\n';} else {cout << tmax - tmin + 1 << ' ' << xmin << ' ' << ymin << ' ' << xmax << ' ' << ymax << '\n';}}return 0;
}