A Huster

0%

math collect

Posted on Edited on Valine:

EXGCD

　　我们在遇见不定方程的时候，总会一筹莫展，但是EXGCD为我们提供了方法，如同

　　$ a x + b y = c $

　　那么我们先从这个这个式子出发：

　　$ax+by=gcd(a,b)$ 　　 $(1)$

　　我们不妨设出另一个式子

　　$ b x_{0}+(a \% b)y_{0}=gcd(b,a \% b)$ 　　 $(2)$

　　Because $gcd(a,b)= gcd ( b , a \% b ) $ ,thus:

　　$a x+b y=bx_{0}+a \% b y_{0}$

　　$a x+b y=bx_{0} +(a-a/b \times b)\times y_{0}$

　　$a x+b y=ay_{0} +b(x_0-a/b \times y_{0})$

　　根据乘法等式，相对应系数的未知数相等，那么就可以得到：

　　$x=y_{0}　　y=x-a/b*y_{0}$　　

　　那么在求gcd的过程中，我们可以在其中不断求解，但是递归到底时返回的x，y值是多少？

　　我们令在b=0时，带入（1）式，那么得到

　　$ax = a$,我们令x=1,y=0即可。

　　然后思考如何求解一开始的那个式子：

　　若有$ax+by=c$，则设$ax_{0}+by_{0}=c$,

　　两式相减：$a(x-x_{0})+b(y-y_{0})=0$

　　移项，除以gcd(a,b):$\frac{a}{gcd(a,b)}(x-x_{0})= - \frac{b}{gcd(a,b)}(y-y_{0})$

　　因为$gcd(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$

　　所以$\frac{b}{gcd(a,b)}$可以整除$(x-x_{0})$

　　即 $\frac{b}{gcd(a,b)} \times t=(x-x_{0}), t \in Z$

　　对于任意x，都可以表示为

　　$x=x_{0}+\frac{b}{gcd(a,b)} \times t$

　　那么根据exgcd求出的特解且$t \in Z$，我们可以这样求出最小解：

　　$x_{min}=x \%(\frac{b}{gcd(a,b)})$

　　在代码中的写法可以是

​ 　$mod=b/gcd(a,b),ans=(x \% mod+mod) \% mod$

　　那么这样我们就解决了$ax+by=gcd(a,b)$最小解问题。

　　如果是 $ax+by=c$ ，只需要两边乘上$\frac{c}{gcd(a,b)}$即可；

　　这里附上 例题

　　并给出模板Code：

　　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int n,m,L,t1,t2;

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;//return gcd  
}

int main(){
    scanf("%d%d%d%d%d",&t1,&t2,&n,&m,&L);
    int x,y;
    if(m<n) swap(m,n),swap(t1,t2);//由于exgcd函数默认a，b为正整数，所以要换一下 
    int gcd=exgcd(m-n,L,x,y);
    cerr<<x*((t1-t2)/gcd)<<endl; 
    if((t1-t2)%gcd!=0) printf("Impossible\n"); //根据推论，应当满足等式两端成立 
    else printf("%lld\n",(1ll*x*((t1-t2)/gcd)%(L/gcd)+L/gcd)%(L/gcd));//正负处理 
}

裴蜀定理

　　这里给出定理的内容，我大概描述一下：

　　对于$a,b$两个整数,且$gcd(a,b)=d$，那么对于任意的$x,y ,ax+by$是d的倍数。

本站访问次数：