yukicoder : No.2104 Multiply-Add

ここら辺は典型かな。
https://yukicoder.me/problems/no/2104

問題

2変数X,Yの初期値はA,Bであるとする。
X,Yに以下の処理を繰り返し、X=C,Y=Dとなるようにしたい。
可能ならその手順を示せ。

• XにYの整数倍を加える
• YにXの整数倍を加える

解法

GをA,B,C,DのGCDとする。
X=A,Y=BからX=Y=Gにするのは互除法の要領で可能である。
同様に、X=G,Y=GをX=C,Y=Dにしたいわけだが、これはX=C,Y=DからX=Y=Gにする手順を巻き戻せばよい。

ll A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D;
	if(A==C&&B==D) {
		cout<<0<<endl;
		return;
	}
	if(A==0&&B==0) {
		cout<<-1<<endl;
		return;
	}
	if(C==0&&D==0) {
		cout<<-1<<endl;
		return;
	}
	ll g1=__gcd(abs(A),abs(B));
	ll g2=__gcd(abs(C),abs(D));
	if(g1!=g2) {
		cout<<-1<<endl;
		return;
	}
	vector<pair<int,int>> V,W;
	while(abs(A)&&abs(B)) {
		if(abs(A)>abs(B)) {
			V.push_back({1,-A/B});
			A-=A/B*B;
		}
		else {
			V.push_back({2,-B/A});
			B-=B/A*A;
		}
	}
	if(A==0) {
		if(B>0) {
			V.push_back({1,1});
			V.push_back({2,-1});
		}
		else {
			V.push_back({1,-1});
			V.push_back({2,1});
		}
	}
	else if(A<0) {
		V.push_back({2,-1});
		V.push_back({1,2});
		V.push_back({2,-1});
	}
	while(abs(C)&&abs(D)) {
		if(abs(C)>abs(D)) {
			W.push_back({1,C/D});
			C-=C/D*D;
		}
		else {
			W.push_back({2,D/C});
			D-=D/C*C;
		}
	}
	if(C==0) {
		if(D>0) {
			W.push_back({1,-1});
			W.push_back({2,1});
		}
		else {
			W.push_back({1,1});
			W.push_back({2,-1});
		}
	}
	else if(C<0) {
		W.push_back({2,1});
		W.push_back({1,-2});
		W.push_back({2,1});
	}
	
	while(W.size()) V.push_back(W.back()),W.pop_back();
	cout<<V.size()<<endl;
	FORR2(a,b,V) cout<<a<<" "<<b<<endl;

	
}

まとめ

もっと短く書けないものかな。