CF #279(Div2) D - Chocolate - ゴリラ系情報系男子大学生の日記

概要 :

二本のチョコバーの縦と横の長さがそれぞれ整数で与えられる。
それらを(水平方向もしくは垂直方向に) $\frac{1}{2}$ を食べるか, $\frac{1}{3}$ を食べるかしてそれらの面積を等しくしたい。この時かかる最小の手数(問題では時間だがここでは手数としておく)を求める。また、最終的な二本の縦と横の長さも出力する。

解法 :
二本のチョコバーの面積をそれぞれ $S_1,S_2$ ,縦、横の長さを $x_1,y_1,x_2,y_2$ とすると
$S_1=x_1 \times y_1=2^a\times 3^b\times n$
$S_2=x_2 \times y_2=2^c\times 3^d\times m$
と表せる。
この時に $n\neq m$ であったならどのような操作をしても同じ面積にはならない。
逆に $n=m$ ならば必ず同じ面積にすることが出来る。

ここでそれぞれの操作について
操作(1): $\frac{1}{2}$ 食べる -> $S$ の因数から2を1つ取り除く
操作(2): $\frac{1}{3}$ 食べる -> $S$ の因数の中の3を2に変える
と言い換えることができるので
まず, $b=d$ になるまで(2)を繰り返し
その後 $a=c$ になるまで(1)を繰り返す

これで最終的に $S_1=S_2$ となる。

#include<iostream>
#include<set>
#include<vector>
using namespace std;


int main(){
	long long x1,y1,x2,y2;
	cin>>x1>>y1;
	cin>>x2>>y2;
	long long ma=max(x1,max(x2,max(y1,y2))); 
	vector<int> s1,s2;
	int n1[2]={0,0},n2[2]={0,0};
	
	long long tmp1=x1,tmp2,tmp;
	while(tmp1%2==0){tmp1/=2;n1[0]++;}
	while(tmp1%3==0){tmp1/=3;n1[1]++;}
	
	tmp2=y1;
	while(tmp2%2==0){tmp2/=2;n1[0]++;}
	while(tmp2%3==0){tmp2/=3;n1[1]++;}
	
	tmp=tmp2*tmp1;
	
	 tmp1=x2;
	while(tmp1%2==0){tmp1/=2;n2[0]++;}
	while(tmp1%3==0){tmp1/=3;n2[1]++;}
	 tmp2=y2;
	while(tmp2%2==0){tmp2/=2;n2[0]++;}
	while(tmp2%3==0){tmp2/=3;n2[1]++;}
	
	
	int co=0;
	if(tmp!=tmp1*tmp2){
		cout<<-1<<endl;
		return 0;
	}

	while(n1[1]>n2[1]){
		n1[1]--;
		n1[0]++;
		co++;
		if(x1%3==0)x1=(x1*2)/3;
		else y1=(y1*2)/3;
	}
	while(n1[1]<n2[1]){
		n2[1]--;
		n2[0]++;
		co++;
		if(x2%3==0)x2=(x2*2)/3;
		else y2=(y2*2)/3;
	}
	while(n1[0]>n2[0]){
		n1[0]--;
		co++;
		if(x1%2==0)x1/=2;
		else y1/=2;
	}
	while(n2[0]>n1[0]){
		n2[0]--;
		co++;
		if(x2%2==0)x2/=2;
		else y2/=2;
	}
	cout<<co<<endl;
	cout<<x1<<" "<<y1<<endl;
	cout<<x2<<" "<<y2<<endl;
}