前置知识——扩展欧几里得算法

用于求 \(ax+by=\gcd(a,b)\) 解。

求一组可行解

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

所以列含参方程得：

\[\begin{cases} ax_1+by_1=\gcd(a,b)\\bx_2+(a\bmod b)y_2=\gcd(b,a \bmod b)\end{cases} \]

于是有:

\[ax_1+by_1=bx_2+(a\bmod b)y_2 \]

\[ax_1+by_1=bx_2+(a-\lfloor \dfrac{a}{b} \rfloor\times b)y_2 \]

\[ax_1+by_1=ay_2+b(x_2-\lfloor \dfrac{a}{b} \rfloor\ y_2) \]

所以：\(x_1=y_2,y_1=(x_2- \lfloor \frac{a}{b}\rfloor y_2)\)，不断递归求解可以得到。

inline int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int t=x;
    x=y,y=t-a/b*y;
    return d;
}

对于上述的方程是一定有解的，并且存在一组 \((x,y)\) 满足 \(|x|\le b,|y| \le a\)，我们称其为裴蜀定理。

求任意一组通解

设已经求出的可行解为 \((x_0,y_0)\)，带入到方程中有：

\[\begin{cases} ax_0+by_0=\gcd(a,b)\\ax+by=\gcd(a,b)\end{cases} \]

联立并整理得：

\[a(x_0-x)=b(y-y_0) \]

\[\dfrac{a}{\gcd(a,b)}(x_0-x)=\dfrac{b}{\gcd(a,b)}(y-y_0) \]

容易发现这个等式左右两边的前一个因式是互质的，因此后一个因式与前一个因式是对应整除关系（根据唯一分解定理可以得到），设这个商为 \(k\)，就有：

\[\begin{cases}x_0-x =\dfrac{b}{\gcd(a,b)}\times k\\\\y-y_0=\dfrac{a}{\gcd(a,b)}\times k\end{cases} \]

整理得到：\(x=x_0-\frac{b}{\gcd(a,b)}\times k,y=y_0+\frac{a}{\gcd(a,b)}\times k\)，其中 \(k\in \mathbb{Z}\)。

推广到不定方程

对于不定方程 \(ax+by=c\)，解决方式如下：

求解 \(ax+by=gcd(a,b)\) 的一组解 \((x_0,y_0)\)，同乘 \(\frac{c}{\gcd(a,b)}\)，就能得到不定方程的一组可行解 \((x,y)=(x_0\times\frac{c}{\gcd(a,b)},y_0\times \frac{c}{\gcd(a,b)})\)，而我们把它代入到通解的式子中，得到最终的结果：

\[\begin{cases} x=\dfrac{c}{\gcd(a,b)}\times x_0- \dfrac{b}{\gcd(a,b)}\times k \\\\ y=\dfrac{c}{\gcd(a,b)}\times y_0+ \dfrac{a}{\gcd(a,b)}\times k\end{cases} \]

特别地，\(x\) 的最小整数解为 \((x \bmod \frac{b}{\gcd(a,b)}+\frac{b}{\gcd(a,b)})\bmod\frac{b}{\gcd(a,b)}\)

分析

下面我们来看这道题，可以得到如下一个式子：

\[a(-x)+by=c \]

设 \(x_0=-x\)，得到：

\[ax_0+by=c \]

当方程有解时，\(\gcd(a,b)\mid c\)，所以 \(c\) 的最小值为 \(\gcd(a,b)\)，第一问套模板即可解决。

第二问的解决相对抽象，可以结合图像来研究：

蓝色的直线表示 \(-5x+3y=1\)，记为 \(l_1\)；绿色的直线表示 \(5x+3y=1\)，记为 \(l_2\)，题目中的要求的是 \(l_1\) 的最小整数解，即点 \(B(x_1,y_1)\)；我们所解的不定方程为 \(l_2\)，可能得到的一组解为点 \(C\)。

因为每一个 \(x\) 都满足 \(x=x_1-\frac{b}{\gcd(a,b)}\times k\ (k\in \mathbb{Z})\)，所以我们可以找到 \(l_2\) 的最小正整数解 \((x_2,y_2)\)，再减去一个 \(\frac{b}{\gcd(a,b)}\) 就得到了最大负整数解 \(A(x_3,y_3)\)（注意 \(0\) 的特判），可以发现：\(x1=-x3\ ,y1=y3\)，按照如上思路运算即可。

实现

inline ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll t=x;
    x=y,y=t-a/b*y;
    return d;
}
int main(){
    ll a=read(),b=read();
    ll x=0,y=0;
    ll d=exgcd(a,b,x,y);
    printf("%lld\n",d);
    x=(x%(b/d)+(b/d))%(b/d);
    if(x) x-=(b/d);
    y=(d-a*x)/b;
    printf("%lld %lld\n",-x,y);
    return 0;
}