扩欧,80pts求助,代码有注释
查看原帖
扩欧,80pts求助,代码有注释
305854
Drind楼主2023/7/3 09:02

WA了两个点#5,#10

#include<bits/stdc++.h>
using namespace std;

long long exgcd(long long a,long long b,long long &x,long long &y){//扩欧板子
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	long long k=exgcd(b,a%b,x,y);
	long long t=x;
	x=y;
	y=t-(a/b)*y;
	return k;
}

int main()
{
	long long x,y,m,n,L,a,b,gcd,tmp;
	cin>>x>>y>>m>>n>>L;//列出方程x+km=y+kn(mod L),化为同余方程k(m-n)=y-x(mod L),其中k为碰面需要的次数
	tmp=((y-x)%L+L)%L;//%L+L%L保证y-x为正
	gcd=exgcd(((m-n)%L+L)%L,L,a,b);
	if(tmp%gcd!=0){//判断同余方程是否有解
		cout<<"Impossible\n";
		return 0;
	}
	a=a/gcd*tmp;//裴蜀定理扩倍
	a=(a%L+L)%L;//保证答案为最小正整数
	cout<<a<<endl;
}
2023/7/3 09:02
加载中...