裴蜀定理

对于任意正整数 \(a,b\)，记 \(g=(a,b)\)，一定存在整数 \(x,y\)，使得 \(ax+by=g\)，且能凑出的数一定是 \(g\) 的倍数。

首先由于 \(a,b\) 都是 \(g\) 的倍数，所以能凑出的数必定是 \(g\) 的倍数。

关键在于怎么证明一定存在整数 \(x,y\)，使得 \(ax+by=g\)。

下面我们就抛出这个算法。

扩展欧几里得算法

首先引入欧几里得算法。

\(g=\gcd(b,a\bmod b)\)（不知道就回普及组来学的实在太强了）

若 \(b=0\)，则 \(g=a\)。

直接在欧几里得算法里添加内容。

我们从边界情况开始考虑。

当 \(b=0\) 时，要求 \(ax+by=ax=\gcd(a,0)=a\)，显然 \(x=1,y=0\) 是一组解。

我们在递归的时候将 \(x,y\) 翻转，于是就求得 \(by+(a\bmod b)x=\gcd(b,a\bmod b)=g\)。

根据余数的定义 \(a\bmod b=a-b\lfloor\dfrac{a}{b}\rfloor\)。

代入可得 \(by+(a-b\lfloor\dfrac{a}{b}\rfloor)x=g\)。

我们将 \(a,b\) 系数整理到一块儿。

\(ax+b(y-\lfloor\dfrac{a}{b}\rfloor x)=g\)。

发现这就是我们需要的形式，于是令 \(y=y-\lfloor\dfrac{a}{b}\rfloor x\)。

那怎么求多组解呢？

发现 \(a(x-\dfrac{b}{d})+b(y+\dfrac{a}{d})=ax+by\)。

那么我们据此可以推出所有的解。

令 \(x_0,y_0\) 表示我们求得的解。

则所有解 \(x=x_0-k\dfrac{b}{d},y=y+k\dfrac{a}{d}\)。

据此发现有无数个解。

扩欧直接应用

#include<cstdio>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while

const int N=1;
int n;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    scanf("%d",&n);
    W(n){
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

应用：求解 \(ax\equiv b\pmod{m}\)（当 \(b=1\) 时，\(x\) 为 \(a\) 的逆元）

题目传送门

考虑变形可得 \(ax=my+b\bmod m\)，也可以变为 \(ax=my+b\)（就是将部分的 \(m\) 给 \(b\)）。

得 \(ax-my=b\)。

令 \(y'=-y\)，\(ax+my'=b\)。

先用扩欧解 \(b=(a,m)\) 的情况，然后先判断是不是倍数，然后扩大 \(\dfrac{b}{(a,m)}\)。

#include<cstdio>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while

const int N=1;
int n;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    scanf("%d",&n);
    W(n){
        // printf("n=%d\n",n);
        int a,b,m,x,y;
        scanf("%d%d%d",&a,&b,&m);
        int d=exgcd(a,m,x,y);
        if(b%d)puts("impossible");
        else printf("%lld\n",1ll*b*x/d%m);
    }
    return 0;
}