Week10：Game23——分解质因数

题目描述
给出两个数字n和m，目的是将n转变成m。n有两种操作：乘以2或者乘以3，操作数量不限，输出将n转换成m的操作次数，如果转换不了输出-1。

输入格式
输入的唯一一行包括两个整数n和m（1<=n<=m<=5*10^8).

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

输入输出案例

Simple Input 1
120 51840
Simple Output 1
7

Simple Input 2
42 42
Simple Output 2
0

Simple Input 3
48 72
Simple Output 3
-1

解题思路
首先判断目标m与初始值n的关系：如果m都不能被n整除，那直接-1就可。
如果能够被n整除：获取div=m/n，对于这个div：

  • 如果它能够被2整除，就一直整除直到不能为止，储存整除的次数。
  • 如果它能够被3整除，就一直整除直到不能为止，储存整除的次数。
  • 这么一通操作下来，如果最后div的结果不是1，那就说明div的质因数里还有除了2和3以外的质数，输出-1即可。

给出代码：

#include <iostream>
#include <vector>using namespace std;int main()
{int n, m;cin >> n >> m;if (m % n != 0){cout << -1 << endl;return 0;}if (m == n){cout << 0 << endl;return 0;}int counter = 0;int div = m / n;while (!(div % 2)){counter++;div /= 2;}while (!(div % 3)){counter++;div /= 3;}if (div != 1){cout << -1 << endl;return 0;}cout << counter << endl;return 0;}

Week10：Game23——分解质因数

题目描述
给出两个数字n和m，目的是将n转变成m。n有两种操作：乘以2或者乘以3，操作数量不限，输出将n转换成m的操作次数，如果转换不了输出-1。

输入格式
输入的唯一一行包括两个整数n和m（1<=n<=m<=5*10^8).

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

输入输出案例

Simple Input 1
120 51840
Simple Output 1
7

Simple Input 2
42 42
Simple Output 2
0

Simple Input 3
48 72
Simple Output 3
-1

解题思路
首先判断目标m与初始值n的关系：如果m都不能被n整除，那直接-1就可。
如果能够被n整除：获取div=m/n，对于这个div：

  • 如果它能够被2整除，就一直整除直到不能为止，储存整除的次数。
  • 如果它能够被3整除，就一直整除直到不能为止，储存整除的次数。
  • 这么一通操作下来，如果最后div的结果不是1，那就说明div的质因数里还有除了2和3以外的质数，输出-1即可。

给出代码：

#include <iostream>
#include <vector>using namespace std;int main()
{int n, m;cin >> n >> m;if (m % n != 0){cout << -1 << endl;return 0;}if (m == n){cout << 0 << endl;return 0;}int counter = 0;int div = m / n;while (!(div % 2)){counter++;div /= 2;}while (!(div % 3)){counter++;div /= 3;}if (div != 1){cout << -1 << endl;return 0;}cout << counter << endl;return 0;}