20分代码求调
查看原帖
20分代码求调
572482
Dream_weavers楼主2022/1/17 16:05

思路:扩欧

QAQ

#include<iostream>
#define int long long
using namespace std;
int x,y,ans;
int exgcd(int a,int b,int x,int y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	ans=exgcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-(a/b)*y;
	return ans;
}
signed main(){
	int n,m,x1,y1,L;
	int a,b;
    cin>>x>>y>>m>>n>>L;
	a=x-y,b=n-m;
	if(b<0)
	    a=-a,b=-b;	
	
	exgcd(b,L,x,y);
	
	if(a%ans!=0)
	    cout<<"Impossible";
	else 
	    cout<<((x*(a/ans))%(L/ans)+(L/ans))%(L/ans);
    return 0;
}

2022/1/17 16:05
加载中...