80分求调
查看原帖
80分求调
923645
YJDAK楼主2023/8/14 18:19

扩欧,样例对了但80分,大佬们帮我找下错呗qwq

#include<iostream>
using namespace std;
typedef long long ll;
ll GCD,X,Y;
void exgcd(ll a,ll b)
{
    if(b==0)
	{
        X=1;
        Y=0;
        GCD=a;
        return ;
    }
    exgcd(b,a%b);
    swap(X,Y);
    Y-=a/b*X;
}

int main(){
    ll x,y,n,m,l;
    cin>>x>>y>>m>>n>>l;
    ll c=y-x;
    ll b=l;
	ll a=m-n;
    if(a<0){
        a=-a;
        c=-c;
    }
    exgcd(a,b);
    if(c%GCD) 
    {
    	cout<<"Impossible";
    	return 0;
	} 
    X=X*c/GCD;
    Y=Y*c/GCD;
    if(a<0)
    {
    	X=-X;
	}
	if(b<0)
	{
		Y=-Y;
	}
    cout<<(X%b+b)%b;
}

2023/8/14 18:19
加载中...