数论是学习OI的自闭之路。QAQ

问题如下:

求不定方程的整数解

ax+by=gcd(a,b)ax+by=\gcd(a,b)

的解。

通过欧几里得原理:

gcd(a,b)=gcd(b,a%b)\gcd(a,b)=\gcd(b,a\%b)

那么原式可化为:

bx+a%by=gcd(b,a%b)bx'+a\%by'=gcd(b,a\%b)

那么只需求出xxxx'yyyy'的关系即可:

bx+a%by=gcd(b,a%b)=gcd(a,b)=ax+by\begin{aligned} bx'+a\%by'&=gcd(b,a\%b)\\=\gcd(a,b)&=ax+by\\ \end{aligned}

将含aa与含bb的合并

bx+a%by=ax+bybx+ayabb×y=ax+byb(xyab×y)+a(yx)=0\begin{aligned} &bx'+a\%by'=ax+by\\ &bx'+ay'-\lfloor\frac{a}{b}\rfloor b\times y'=ax+by\\ &b(x'-y-\lfloor\frac{a}{b}\rfloor\times y')+a(y'-x)=0 \end{aligned}

已知该式恒成立,则:

x=yy=xab×y\begin{aligned} x&=y'\\ y&=x'-\lfloor\frac{a}{b}\rfloor\times y' \end{aligned}

再利用辗转相除的函数递归计算xxyy即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
int x,y;

int exgcd(int a,int b) {
if(b==0) {x=1,y=0;return a;}
int g=exgcd(b,a%b);
int oldx=x,oldy=y;
x=oldy;
y=oldx-a/b*oldy;
return g;
}

这里需要注意的是,递归的边界为x=1,y=0x=1,y=0时的一组特解。

那么将此式拓展为一般结论,即求解:

ax+by=cax+by=c

首先讨论有无解,当gcd(a,b)c\gcd(a,b)\nmid c一定无解,这里就不给出证明。我们另k=cgcd(a,b)k=\frac{c}{\gcd(a,b)}

axk+byk=gcd(a,b)×k=cax'k+by'k=\gcd(a,b)\times k=c

就得到了x=xkx=x'ky=yky=y'k

如果要求xx非负且最小,另t=bgcd(a,b)t=\frac{b}{\gcd(a,b)},则(x%t+t)%t(x\%t+t)\%t就是xx的最小非负解。加tt主要是为了处理负数的问题。

有关例题:

评论