扩欧求调
查看原帖
扩欧求调
664744
_lqs_楼主2023/5/4 13:07
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,i,j,ans,a,b,c,x,y,L,p,k,d;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
void exgcd(int a,int b,int c){
	if(b==0){
		p=c/a,k=0;
		return;
	}
	exgcd(b,a%b,c);
	int tmp=p;
	p=k,k=tmp-(a/b)*k;
}
signed main(){
	scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
	d=gcd(L,abs(n-m));
	if(abs(x-y)%d!=0){
		printf("Impossible");
		return 0;
	}
	exgcd(L,abs(n-m),abs(x-y));
	if(n-m<0) k=-k;
	if(x-y<0) k=-k;
	if(k>0) k%=L;
	else{
		if((-k)%L==0) k=0;
		else{
			int cnt=(-k)/L+1;
			k=k+cnt*L;
		}
	}
	printf("%lld",k);
	return 0;
}

/*
k步 
x+km同余y+kn (mod L)
L | (x+km-y-kn)
pL=x+km-y-kn
pL-km+kn=x-y  ->   (p)L+(k)(n-m)=x-y 
*/
2023/5/4 13:07
加载中...