(luogu1516) 青蛙的约会

发表于 分类于 ，

原题链接

思路:

首先列出式子:

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

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

两者若能相遇，则有:

\[ \begin{aligned} & x+tm \equiv y+tn (mod\ L) \\ \iff & (m-n)t \equiv y-x(mod\ L) \end{aligned} \]

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

代码:

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;
}