Exgcd 学习笔记
引理
Bézout's theorem
对于 \(gcd(a,b)=d\) 的情况,一定 \(\exists x,y\) ,使得 \(ax+by=d\) 成立。相反的,当解方程 \(ax+by=c\) 时,若 \(c\) 不是 \(d\) 的倍数,那么此方程一定无解。
Exgcd 推导
我们知道如何通过辗转相除法求出 \(gcd(a,b)\) ,那么结合贝祖定理,不难发现方程 $bx+(a\mod b)y =d $ 和上述方程一定有相同的解,更极限地想,当 \(a\equiv0\mod b\) 时,方程变成了 \(a'x=d\) ,而根据辗转相除法,此时的 \(a'\) 一定等于 \(d\) ,所以解为 \(x=1,y=\text{any_number}\) ,假设我们在递归的过程中知道了当层的解,那么可不可以借此推至上一层的解呢?答案是肯定的。
\(a\mod b\) 实际上就是 \(a-\lfloor\frac{a}{b} \rfloor\times b\) ,那么方程经过一次迭代之后就变成了 \(bx+(a-\lfloor\frac{a}{b} \rfloor\times b)y=d\) ,整理一下就可以得到 :
\(ay+b(x-\lfloor\frac{a}{b} \rfloor y)=c\) ,,此时方程达到同构,那么在我们知道 \(x,y\) 的值的情况下面就可以很自然地算出上一层递归中 \(x,y\) 的值分别是多少,这一效果在我们递归到刚刚提到的最后一层的时候就可以达到。
代码如下:(顺带求了个 \(gcd\) )
inline int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int tmpx,tmpy;
int d=exgcd(b,a-(a/b)*b,tmpx,tmpy);
x=tmpy,y=tmpx-(a/b)*tmpy;
return d;
}
如何获得一般解?
我们得到的不过是一组可行解,那么如何由这组可行解推知一般解呢?
考虑如下构造:
\[a(x_0+p)+b(y_0+q)=c \]同时我们也有刚刚得到的 :
\(ax_0+by_0=c\)
整理就可以得到 $ap+bq=0\iff p=-\frac{b}{a}q $ ,首先要使得其为整数,那么结合约分的过程,我们知道必要条件是 \(\frac{a}{gcd(a,b)}|q,\frac{b}{gcd(a,b)}|p\) ,两者只需要满足一个,另外一个就自动满足了。那么我们就可以得到 \(p,q\) 取值的一般形式:
\[\begin{cases}p=t\times \frac{b}{d}\quad x=x_0+p\\q=-t\times \frac{a}{d} \quad y=y_0+q\end{cases} \]如何获得有限制的解
即一组正整数解,以及此时 \(x,y\) 各自的最大最小取值;或者没有正整数解的时候 \(x,y\) 分别的最小正整数取值。
通过令 \(x>0\) ,发现需要让 \(t>-x_0\times \frac{d}{b}\) ,那么 \(t\) 的最小值就是 \(\lfloor-x_0\times \frac{d}{b}\rfloor+1\)
同理令 \(y>0\) ,发现需要让 \(t<y_0\times \frac{d}{a}\) , 那么 \(t\) 的最大值就是 \(\lceil y_0\times \frac{d}{a}\rceil-1\)
我们只需要去验证当 \(t\) 取到最小最大值的时候另一个数是否也为正整数即可,事实上我们只需要验证一组即可。
代码如下 :
inline void solve(int a,int b,int c)
{
if(c%gcd(a,b)!=0)
{
puts("-1");
return ;
}
int f=c/gcd(a,b),x,y;
int d=exgcd(a,b,x,y);
x*=f,y*=f;
int t,tmpt;
t=(int)floor(-1.0*d*x/b)+1;
tmpt=(int)ceil(1.0*d*y/a)-1;
if(y-t*a/d<=0)
wr(x+t*b/d),putchar(' '),wr(y-tmpt*a/d),putchar('\n');
else
printf("%lld %lld %lld %lld %lld\n",abs(t-tmpt)+1,x+t*b/d,y-tmpt*a/d,x+tmpt*b/d,y-t*a/d);
}
标签:lfloor,frac,gcd,int,笔记,times,学习,tmpy,Exgcd
From: https://www.cnblogs.com/Hanggoash/p/18430082