exgcd 80pts WA5,10求助
查看原帖
exgcd 80pts WA5,10求助
373198
WhileTrueRP楼主2023/8/27 11:33
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b)return x=1,y=0,void();
	exgcd(b,a%b,y,x),y-=a/b*x;
}
int main(){
	ll x,y,m,n,L,x0,y0;
	scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
	if(n<m)swap(m,n),swap(x,y);
	ll a = m-n,b = L;
	ll d = __gcd(a,b);
	exgcd(a,b,x0,y0);
	if((y-x) % d !=0){
		puts("Impossible");
		return 0;
	}
	printf("%lld",((y-x)*x0/d+L)%L);
}
720934988 996392308 1675670875 794994043 182443922

正解:3987081 错解:95209042

2023/8/27 11:33
加载中...