题解：P5656 【模板】二元一次不定方程 (exgcd)

_Weslie_ · 2025-10-17 21:09:33 · 题解

这是有必要的。因为我 CSP-S 考前两个周还不会 exgcd。

upd 10.27 修锅。

::::warning[前置知识]

• 特别地，我们规定 \gcd(x,0)=x。 ::::

exgcd，全称扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 ax+by=\gcd(a,b) 的一组可行解。

算法过程

它与 gcd 是类似的。

回顾一下普通 gcd 的过程：

:::::info[如果你不知道欧几里得算法（gcd）] 欧几里得算法（gcd）可以在 \operatorname{O}(\log V) 的时间复杂度内求出两个数的最大公约数。

它的过程是这样的：

• 假设当前要求 \gcd(a,b)。
• 如果 b=0，那么 \gcd(a,0)=a（人为规定的），于是返回。
• 否则，递归求解 \gcd(b,a\bmod b) 的值，并返回。

在这一过程中，我们用到了一个定理 \gcd(a,b)=\gcd(b,a\bmod b)。证明在 OI Wiki 上有。

那么它的复杂度为何是 \operatorname{O}(\log n) 的呢？

::::info[gcd 为何是 \operatorname{O}(\log n) 的] 先看 \log 底数：它是 2。

我们考虑当前的 \gcd(a,b)。

那么接下来它会有以下两种情况：

每次走上面的情况时，下一次都一定会走下面的情况，而 2\times (a\bmod b)\le a，所以复杂度是 \operatorname{O}(\log V) 的。 :::info[为何 2\times (a\bmod b)\le a？] 考虑令 b=\lfloor\dfrac{a}{2}\rfloor+1，则 a\bmod b=\lfloor\dfrac{a}{2}\rfloor-1（a 为偶数）或 \lfloor\dfrac{a}{2}\rfloor（a 为奇数）。

如果 b 更大，那么 a\bmod b=a-b 更小。

如果 b 更小，可以证明 a\bmod b\le b\le \dfrac{a}{2}。 ::: ::::

:::::

那么我们如果要求 ax+by=\gcd(a,b) 的解，是否可以先求出 bx+(a\bmod b)y=\gcd(b,a\bmod b) 的解？

是可以的。假设下面方程的一组解是 x_0,y_0，则上面方程的解如下：

::::success[证明] 考虑设 a=kb+c，容易注意到：

证毕。 ::::

但是我们不能无限制的递归下去。我们需要找寻一个边界条件。它就是 b=0 的时候，这时我们直接返回

即可。

证明：显而易见的。直接把它代入原方程。

::::success[一个简单的 exgcd 代码实现]

#define ll long long
ll x,y;
void exgcd(ll a,ll b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    ll t=x;
    x=y;
    y=t-a/b*y;
}

你还可能见到另外一种写法。

void exgcd(ll &x,ll &y,ll a,ll b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(x,y,b,a%b);
    ll t=x;
    x=y;
    y=t-a/b*y;
}

这里面的 & 是取地址符，具体来说，当你递归调用时，如果内层的 x,y 被改变了，它会连带着外层的 x,y 一起改变。 ::::

例题 1

例题 1：P1082 [NOIP 2012 提高组] 同余方程

求关于 x 的同余方程 a x \equiv 1 \pmod {b} 的最小正整数解。

对于 100\% 的数据，2 ≤a, b≤ 2,000,000,000。

::::success[Solution] 正常我们解决 exgcd 问题都需要 a,b 两个常量，但是这题只有 1 个。

没关系！我们只需要把方程转化为 ax+by\equiv 1(\pmod b) 即可。

由于 by\equiv 0，所以 y 是多少对答案并不重要。

但是 exgcd 解出来的只是一组解，所以我们要把解出来的 x_0 对 b 取模来求解。

因为 x_0 有可能是负数，所以应该先让 x\leftarrow x_0\bmod b，然后再让 x\leftarrow x+b。但是若是 x_0 初始就是整数，这样会让 x+b 不是最小正答案，所以还需要让 x\leftarrow x\bmod b。 :::success[Code]

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll x,y;
void exgcd(ll a,ll b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    ll t=x;
    x=y;
    y=t-a/b*y;
}
int main(){
    ll a,b;
    cin>>a>>b;
    exgcd(a,b);
    x=(x%b+b)%b;
    cout<<x;
    return 0;
}

::: ::::

变式 1

变式 1：P2613 【模板】有理数取余

求 bx\equiv a\pmod {19260817} 的解。

::::success[Solution] 如果我们求出 bx\equiv 1\pmod {19260817} 的根 x_0，那么 ax_0 就是符合条件的 x 之一。

:::error[为什么 ax_0 是符合条件的 x 之一！] 因为 bx_0\equiv 1，那么 abx_0\equiv a。 :::

把上面的代码改一改就能过。 ::::

事实上，这个变式的意义是可以通过 exgcd 来求任意一个整数的逆元，相比起费马小定理与快速幂的组合，适用范围更广。

例题 2

例题 2：P5656 【模板】二元一次不定方程 (exgcd)

exgcd 基础，【模板】exgcd 就不基础。

对于普通的 exgcd，它有非常多的不同。

裴蜀定理的应用

正常的 exgcd 是解 ax+by=\gcd(a,b)，但是 P5656 是解 ax+by=c！

别怕，我们假设 ax+by=\gcd(a,b) 已经解出来了 x_0,y_0。

那么 ax+by=c 的解会是多少呢？

不难发现 a\dfrac{x_0c}{\gcd(a,b)}+b\dfrac{y_0c}{\gcd(a,b)}=c。

所以我们需要保证 \dfrac{x_0c}{\gcd(a,b)} 和 \dfrac{y_0c}{\gcd(a,b)}，也就是 c\bmod \gcd(a,b)=0。

如果不等于零，可以直接判断没有整数解。

:::info[为何“如果不等于零，可以直接判断没有整数解”？] 这就是裴蜀定理。P4549 题解区有关于这个的证明。 :::

但是现在我们要求它的正整数解的数量，所有正整数解中 x 的最小值，所有正整数解中 y 的最小值，所有正整数解中 x 的最大值，以及所有正整数解中 y 的最大值，或所有整数解中 x 的最小正整数值，y 的最小正整数值。

我们发现这个东西显然是不可能用普通的 exgcd 做了。假设我们现在已经通过 exgcd + 裴蜀定理解决了 ax+by=c 的一组特殊解，那么我们该如何求出它的正整数解的数量，所有正整数解中 x 的最小值，所有正整数解中 y 的最小值，所有正整数解中 x 的最大值，以及所有正整数解中 y 的最大值，或所有整数解中 x 的最小正整数值，y 的最小正整数值呢？

基础：单推多

这个是以下推导的基础。

首先，我们设一组普通解为 x,y。

那么显然有：

我们设 x-x_0=\triangle x，y-y_0=\triangle y。

那么有：

于是得到

由于 ax_0+by_0=c，所以

这是一个非常神秘的式子。我们需要找一组通解。

直接给结论：

其中 p 是任意整数。

:::info[怎么找到的通解？]

考虑人脑是如何解这个方程的，以 4x+6y=0 为例。

不难考虑让 x=6，y=-4。

也就是说，令

就可以得到一组特解。

但是 p 必须是一个整数，所以你必须要让 |x| 与 |y| 尽可能小。

所以我们考虑令

:::

那么我们得到

x 的最小值

根据

我们需要求出最大的 p 使得

考虑推导。

最后一步取上等是因为我们不能让 x_{min}=0。

于是可以 \operatorname{O}(1) 求。

:::info[二分方案（不推荐）]

用二分求解 p。

显然 p 满足单调性，p 越大，x 越小。

缺点是该做法的复杂度是 \operatorname{O}(\log V) 的。而且需要给定 p 的范围，万一 x_0 巨大那就不好解了。所以我们不使用这种方法。 :::

y 的最大值

考虑

反解得到

在 \mathbb R 上单调递减。

那么只要 x 取到 x_{min}，那么 y 就能取到 y_{max}。

正整数解的判断

只要 y_{max}\le 0，那么就没有正整数解。

y 的最小值

先给结论：

证明：

考虑下面的方程：

由于

设 \triangle x=x_{max}-x_{min}，\triangle y=y_{min}-y_{max}。

根据上面的推导，可以得到

其中 p 是任意整数。

由于

说明

由于 y_{min} 必须是最小正整数，所以 y_{min}=y_{max}\bmod \dfrac{a}{\gcd(a,b)}。

但是这样并不严谨：因为 y_{max} 可能是 \dfrac{a}{\gcd(a,b)} 的倍数。所以必须加上这种情况。

正整数解的个数

给结论：设答案为 ans，则

我们考虑用小学的植树问题来证明这个结论。

现在有一排树，间隔相等为 d，第一棵树坐标为 x_1，最后一棵树坐标为 x_n，那么一共有多少棵树？（保证 x_n-x_1 是 d 的倍数）

这个是很简单的：答案是 \dfrac{x_n-x_1}{d}+1。

考虑 (x_1,x_n] 内，一定是每 d 个坐标才出现一棵树，所以是区间长度与树的间距之比。由于你没有算第一棵树，所以要加 1。

现在我们考虑把这个问题代入到当前的情况。

把 y 摁到数轴上，然后看作：第一棵树坐标 y_{min}，最后一棵树坐标 y_{max}。

根据上面的推导，树的间距是 \dfrac{a}{\gcd(a,b)}。

所以你就能解了。

:::info[为何每 \dfrac{a}{\gcd(a,b)} 个数就会有一组解？] 很好理解。

考虑

那么

那么存在一组解 x',y'：

由于是在 (y_{min},y_{max}] 区间查找，所以 x,y\ge 1 恒成立。

于是证毕。 :::

x 的最大值

这是很简单的。

由于 y_{min} 已知，所以直接把 y_{min} 代进去就行。

::::error[我们没有处理无正整数解的情况！] 其实不难发现，经过上面的讨论，我们已经把没有正整数解的情况的 x_{min} 与 y_{min} 解出来了。

你还记得 p\ge \lceil\dfrac{1-x_0}{\frac{b}{\gcd(a,b)}}\rceil 吗？此时的 p 就是满足 x_{min}\ge 0 的最小的 p。

同理我们可以发现 y_{min} 在这个条件下依然成立。 ::::

::::success[P5656 代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,y;
void exgcd(ll a,ll b){
    if(b==0){
        x=1;y=0;return;
    }
    exgcd(b,a%b);
    ll t=x;
    x=y;y=t-a/b*y;
}
ll a,b,c;
void solve(){
    scanf("%lld%lld%lld",&a,&b,&c);
    ll g=__gcd(a,b);
    if(c%g!=0){
        printf("-1\n");return;
    }
    exgcd(a,b);
    ll x0=c/g*x,y0=c/g*y;
    ll p=ceil(1.0*(1-x0)/(b/g));
    ll xmin=x0+p*(b/g);
    ll ymax=y0-p*(a/g);
    if(ymax<=0){
        ll ymin=(ymax%(a/g)+(a/g))%(a/g);
        if(ymin==0)ymin=a/g;
        printf("%lld %lld\n",xmin,ymin);
    }
    else{
        ll ymin=(ymax)%(a/g);
        if(ymin==0)ymin=a/g; 
        ll cnt=(ymax-ymin)/(a/g)+1;
        ll xmax=(c-b*ymin)/a;
        printf("%lld %lld %lld %lld %lld\n",cnt,xmin,ymin,xmax,ymax);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)solve();
}

::::

例题 3

P9796 [NERC 2018] Fractions

给你一个整数 n，你需要构造出若干个形如 \dfrac{a_i}{b_i} 的真分数，使得 \sum^k_{i=1} \frac{a_i}{b_i} = 1 - \frac{1}{n}，且 b_i 可以整除 n。

::::info[Solution] 先给结论。

结论：如果有解，一定存在一组 (a,b,x,y)，使得 \dfrac{x}{a}+\dfrac{y}{b}=\dfrac{n}{n-1}；如果上述条件不成立，则无解。

证明：考虑通分。

根据裴蜀定理，上面方程有解的条件是 \dfrac{ab(n-1)}{n} \bmod \gcd(a,b)=0，也就是 n-1 \bmod \gcd(a,b)=0（n 是 a,b 的倍数）。

设 n 为 p_1^{q_1}p_2^{q_2}\cdots p_k^{q_k}。

由于 n-1 与 n 没有除了 1 之外的其他公因数，而 a,b 都是 n 的因数，所以只能让 \gcd(a,b)=1。

考虑令 a=p_x^{q_x}（其中 x\in[1,k]），b=\dfrac{n}{a}，这样 a,b 之间没有公因数，则 \gcd(a,b)=1，符合条件，可以构造出解。

但是如果 k=1，则 b=1，显然不能够造出真分数使得有解，所以报告无解。

如果你构造多个，条件更强，更无法满足。

找出 a,b 之后，只需要解不定方程 ax+by=\dfrac{ab(n-1)}{n}，也就是 ax+by=n-1 即可。

可以用 exgcd 求出其的一组解，然后用 P5656 的代码求出其最小的正整数 x 和最大的正整数 y 来求正整数解。

:::success[AC Code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,y;
void exgcd(ll a,ll b){
    if(b==0){
        x=1;y=0;return;
    }
    exgcd(b,a%b);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
}
//const int N=;
int main(){
    scanf("%lld",&n);
    ll a=-1,b=0;
    ll t=n;
    for(int i=2;i*i<=t;i++){
        if(n%i!=0)continue;
        ll tmp=1;
        while(t%i==0){
            t/=i;tmp*=i;
        }
        if(t==1){
            printf("NO\n");
            return 0;
        }
        a=tmp;b=n/tmp;
        break;
    }
    if(a==-1){
        printf("NO\n");
        return 0;
    }
    exgcd(a,b);
    printf("YES\n2\n");
    ll g=__gcd(a,b);
    ll x0=(n-1)*x,y0=(n-1)*y;
    ll p=ceil(1.0*(1-x0)/(b/g));
    ll xmin=x0+p*(b/g);
    ll ymax=y0-p*(a/g);
    printf("%lld %lld\n%lld %lld",xmin,b,ymax,a);
    return 0;
}

::: ::::