数的变换

问题描述

有一个数字 n，目标是把它转换成 m，在每一步操作中，可将 n 乘以 2 或乘以 3，可进行任意次操作。输出将 n 转换成 m 的操作次数，如果转换不了输出-1。

Input

输入的唯一一行包括两个整数 n 和m（1 ≤ n ≤ m ≤ 5 × 10^8).

Output

输出从 n 转换到 m 的操作次数，否则输出-1。

Sample

Input: 
120 51840
Output: 
7

Input: 
42 42
Output: 
0

Input: 
48 72
Output: 
-1

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

若 n 比 m 大或 m 不是 n 的整数倍，显然是不可操作的。

若 n = m，无需操作。

然后 m ÷ n，得商。

接下来对商操作，多次除以3，直至无法整除；然后多次除以2，直至无法整除。若此结果商不为1，则无法操作，否则可以把 n 变成 m。

计算以上整除次数即可。

源代码

#include <iostream>
#include <cmath>
using namespace std;

long long solve(long long n, long long m) {
	if (n == m)
		return 0;
	if (n > m || m % n != 0)
		return -1;

	long long quotient = m / n;
	// 2^x   3^y
	
	long long cnt2 = 0;
	while (quotient % 2 == 0) {
		cnt2++;
		quotient /= 2;
	}
	long long cnt3 = 0;
	while (quotient % 3 == 0) {
		cnt3++;
		quotient /= 3;
	}
	if (quotient != 1)
		return -1;
	return cnt2 + cnt3;
}

int main() {
	long long n, m;
	while (!(cin >> n >> m).eof()) {
		long long res = solve(n, m);
		cout << res << endl;
	}
	return 0;
}