首页 > 代码库 > 青蛙的约会

青蛙的约会

2024-11-23 01:36:39   203人阅读

传送门

题目描述

求 x+m*t≡y+n*t (mod l)

题解

将上式

转换一下...

x-y≡(n-m)*t(mod l)

(n-m)*t+l*k=x-y...

然后用扩展欧几里得求...

因为我们用扩展欧几里得求出的是(n-m)*t+l*k=gcd(n-m,l)=(x-y)/k;(当 x-y % gcd(n-m,l) ！=0时无解.

所以答案的 t=扩展欧几里得求出的t*(x-y)/gcd(n-m,l)

又因为要求是最小正整数解..

x=(x0%（b/gcd(a,b))+b/gcd(a,b))%(b/gcd(a,b))即为x的最小整数解。

至于为什么..戳这里

代码

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
LL a,t,k,x,y,z,m,n,l,ans;

LL gcd(LL x,LL y){
    return y==0?x:gcd(y,x%y);
}

void exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    z=x;x=y;y=z-a/b*y;
}

int main(){
    scanf("%d%d%d%d%d",&x,&y,&m,&n,&l);
    a=m-n;k=y-x;
    t=gcd(a,l);
    if(k%t!=0){
        printf("Impossible\n");
        return 0;
    }
    exgcd(a,l,x,y);
    l=l/t;if(l<0)l=-l;
    x=x*k/t;
    printf("%d\n",(x%l+l)%l);
    return 0;
}

 

青蛙的约会


联系
我们