数学专题B2—裴蜀定理 P4549 裴蜀定理 裴蜀定理 ax+by=\text{gcd}(x,y) 题目思路 显然由前置知识可知： 对于当前的 ans 和 A_i， ans=\text{gcd}(ans,|A_i|) 所以代码如下： #include using namespace std; #define int long long signed main(){ int n,x,ans; cin>>n>>ans; for(int i=2;i>x; ans=abs(__gcd(ans,abs(x))); } cout `#include using namespace std; #define int long long signed main(){ int n,x,ans; cin>>n>>ans; for(int i=2;i cin>>x; ans=abs(__gcd(ans,abs(x))); } cout 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; } `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 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 `#include 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 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 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 `#include 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(a10) a1=-a1,c1=-c1; g=exgcd(a1,b1); if(c1%g) cout"Impossible"; else cout return 0; }`
数学专题B2—裴蜀定理
笔记