(luogu1516)青蛙的约会

发表于 | 分类于 ，

原题链接

思路:

首先列出式子:

青蛙A在跳跃t次后坐标为$x+tm\ mod\ L$.

青蛙B在跳跃t次后坐标为$y+tn\ mod\ L$.

两者若能相遇, 则有:

所以本题实质上就是求线性同余方程的最小正整数解.

代码:

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
#include <cstdio>
#define int long long   //防止溢出
int exgcd(int a,int b,int& x,int& y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    int g = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return g;
}

signed main() {
    int x,y,m,n,l;
    scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&l);
    int u = ((m-n)%l+l)%l;
    int v = ((y-x)%l+l)%l;
    int t,tmp;
    int g = exgcd(u,l,t,tmp);
    t = (t+l/g)%(l/g);  //化为非负整数
    if(v%g!=0) {    //若v不整除g说明无解
        printf("Impossible");
    } else {
        printf("%lld",t*(v/g)%(l/g));
    }
    return 0;
}