Official

D - Divide by 2 or 3 Editorial by en_translator


\(a_i\) can be uniquely represented as \(a_i=2^{x_i} \times 3^{y_i} \times z_i\) with non-negative integers \(x_i\) and \(y_i\) and a positive integer \(z_i\) not indivisible by \(2\) and \(3\) (considering the prime factorization). Here, the former of the two operations corresponds to decrementing \(x_i\) by \(1\), and the latter to \(y_i\). Since \(z_i\) cannot be changed, because it is a positive integer not indivisible by \(2\) and \(3\), so the answer is -1 if there are \(i\) and \(j\) such that \(z_i \neq z_j\).
Since we cannot increase \(x_i\) and \(y_i\), we need to set each of them to the minimum value \(x_m\) of \(x_i\) and the minimum value \(y_m\) of \(y_i\). On the other hand, letting them below the minimum value is wasteful because it just increases excessive operations. Thus, we can find the answer by finding the number of operations required to let \(x_i\) equal \(x_m\) and \(y_i\) equal \(y_m\), i.e. the sum of differences of \(x_i,y_i\) and \(x_m,y_m\).
In the sample code below, we first find the greatest common divisor \(g\) of \(a_i\) and then consider \(\frac {a_i}{g}\) to find the answer. (note that \(g=2^{x_m} \times 3^{y_m} \times z_i\).)

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N;
	cin>>N;
	
	vector<int> a(N);
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	
	int g = 0;
	for(int i=0;i<N;i++){
		g = gcd(g,a[i]);
	}
	
	int ans = 0;
	
	for(int i=0;i<N;i++){
		a[i] /= g;
		while(a[i]%2==0){
			a[i] /= 2;
			ans++;
		}
		while(a[i]%3==0){
			a[i] /= 3;
			ans++;
		}
		if(a[i]!=1){
			cout<<-1<<endl;
			return 0;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

posted:
last update: