Exgcd 80pts求助
查看原帖
Exgcd 80pts求助
227728
冰糖鸽子TJ鸽子协会楼主2021/2/26 09:34

RT,错的.5和.10

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a,b,m,n,l,x,y,z,X,Y,Z;
int Exgcd(int fx,int fy)
{
	int fz,tmp;
	if(!fy) {x=1;y=0;return fx;}
	fz=Exgcd(fy,fx%fy);
	tmp=x;x=y;y=tmp-(y*(fx/fy));
	return fz;
}
signed main()
{
	cin>>a>>b>>m>>n>>l;
	X=n-m;Y=l;Z=a-b;
	if(X<0) {X=-X;Z=-Z;}
	z=Exgcd(X,Y);
	if(Z%z) {cout<<"Impossible";return 0;}
	x/=z;x*=Z;
	y/=z;y*=Z;
    z=x/Y;
	if(x-z*Y<0) z--;
	cout<<x-z*Y<<endl;
	return 0;
}
2021/2/26 09:34
加载中...