数学专题B2—裴蜀定理
P4549 裴蜀定理
裴蜀定理
$ax+by=\text{gcd}(x,y)$
题目思路
显然由前置知识可知：
对于当前的 $ans$ 和 $A_i$，
$ans=\text{gcd}(ans,|A_i|)$
所以代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,x,ans;
cin>>n>>ans;
for(int i=2;i<=n;i++){
cin>>x;
ans=abs(__gcd(ans,abs(x)));
}
cout<<ans;
return 0;
}P1082 同余方程
扩展欧几里得
扩展欧几里得是用来解决 $ax+by=\text{gcd}(x,y)$ 的一组解的。
设一组解为 $x_1,y_1$，一组解为 $x_2,y_2$
根据欧几里得算法（辗转相除法）可知：$ax_1+by_1=bx_2+(a\ \text{mod} \ b)y_2$，
所以就有：
$$
\begin{align}
ax_1+by_1&=bx_2+(a \ \text{mod} \ b)y_2 \\
ax_1+by_1&=bx_2+(a- b·\lfloor\frac{a}{b} \rfloor)y_2 \\
ax_1+by_1&=ay_2+b(x_2-\lfloor\frac{a}{b} \rfloor y_2) \\
\end{align}
$$
解得：
$$
\begin{cases}
x_1=y_2 \\
y_1=x_2-\lfloor\frac{a}{b} \rfloor y_2
\end{cases}
$$
根据这个递归即可。
代码：
void exgcd(int a,int b){
if(b==0){
/*
通过欧几里得算法（辗转相除法），
最终b一定会变为0，
这个时候gcd(a,b)=a，
所以直接令x=1即可，y可以取任意值
*/
x=1,y=0;
return;
}
exgcd(b,a%b);//传递当前方程
int lx=x;
x=y,y=lx-a/b*y;
}题目思路
题目可以转化为求 $ax+by=1$ 的最小正整数解，
又因为其保证了有解，
所以我们可以知道 $\text{gcd}(a,b)=1$。
所以直接扩欧。
代码：
#include<bits/stdc++.h>
using namespace std;
int A,B,x,y;
void exgcd(int a,int b){
if(b==0){
x=1,y=0;
return;
}
exgcd(b,a%b);
int lx=x;
x=y,y=lx-a/b*y;
}
int main(){
cin>>A>>B;
exgcd(A,B);
x=(x%B+B)%B;//最小正整数解
cout<<x;
return 0;
}P1516 青蛙的约会
题目可以简化为求出一个最小的 $k$ 使得：$x+mk\equiv y+nk\ (\text{mod} \ L)$
开始吟唱：
$$
\begin{align}
x+mk&\equiv y+nk\ (\text{mod} \ L) \\
\therefore x+mk-y-nk&=zL \ (z\in N^*) \\
x-y+k(m-n)&=zL \\
zL+k(n-m)&=x-y \\
\end{align}
$$
令 $x_0=n-m, y_0=L, c=x-y, g=\text{gcd}(M,L)$，
则有 $kx_0+zy_0=c$，
此时就可以用扩欧求出 $kx_0+zy_0=g$ 的一组解。
设该解为 $x_1,y_1$，
则继续吟唱：
$$
\begin{align}
kx_1+zy_1&=g \\
k\frac{x_1c}{g}+z\frac{y_1c}{g}&=c \\
\because k(\frac{x_1c}{g}+dz)+z(\frac{y_1c}{g}-dk)&=c\\
\therefore x_0&=\frac{x_1c}{g}+dz \\
x0 \downarrow &\implies d \downarrow\\
\because db,da&\in N^*, \\
\therefore d_{\text{min}}&=\frac{1}{g}. \\
\therefore x_{0{\text{min}}}&=(\frac{x_1c}{g} \ \text{mod} \ \frac{b}{g} + \frac{b}{g}) \ \text{mod} \ \frac{b}{g} \\
\end{align}
$$
所以得到代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int xx,yy,x,y,m,n,l,g,a1,b1,c1;
int exgcd(int a,int b){
if(b==0){
xx=1,yy=0;
return a;
}
int rtn=exgcd(b,a%b),lx=xx;
xx=yy,yy=lx-a/b*yy;
return rtn;
}
signed main(){
cin>>x>>y>>m>>n>>l;
a1=n-m,b1=l,c1=x-y;
if(a1<0) a1=-a1,c1=-c1;
g=exgcd(a1,b1);
if(c1%g) cout<<"Impossible";
else cout<<((c1*xx/g)%(b1/g)+b1/g)%(b1/g);
return 0;
}
Comments NOTHING