OI

【数论】青蛙的约会

P1516
扩展欧几里得的运用

此题题意为：输入x,y,m,n,l
求使(x+am)%l=(y+an)%l中a的最小正整数解

可以将其先化为不定方程ax+by=c的形式：

=>(x+am)%l+(-y-an)%l=0

=>(x+am-y-an)%l=0

=>x+am-y-an=kl

=>(n-m)a+kl=x-y

由此，可以令a=n-m,b=l,c=x-y，利用扩展欧几里得算法求ax+by=c的最小正整数解；

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<stdio.h>
#include<stdlib.h>
typedef long long ll;

void swap(ll *a,ll *b){
    ll t;
    t=*a;
    *a=*b;
    *b=t;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    return gcd(b,a%b);
}

void extend_euclid(ll a,ll b,ll *x,ll *y){
    if(b==0){*x=1;*y=0;return;}
    extend_euclid(b,a%b,x,y);
    ll t=*x;
    *x=*y;
    *y=t-a/b*(*y);
}

int main(){
    ll m,n,x,y,x1=0,y1=0,l,t;
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    ll a,b,c;
    ll a1,b1;
    if(n-m<0){swap(&n,&m);swap(&x,&y);}
    a=n-m;
    b=l;
    c=x-y;
    t=gcd(a,b);
    if(c%t){printf("Impossible");return 0;}
    extend_euclid(a,b,&x1,&y1);
    b1=b/t;
    x1=((x1*(c/t))%b1+b1)%b1;
    printf("%lld\n",x1);
    return 0;
}

此处要特别注意避免x出现负数.