本文共 1343 字，大约阅读时间需要 4 分钟。

题目来源：

Description

给定一个整数 n，这里定义了如下操作：

1. 如果 n 能被 2 整除，n = n / 2;
2. 如果 n 能被 3 整除，n = 2 * n / 3;
3. 如果 n 能被 5 整除，n = 4 * n / 5。

举例说明，对于整数 30，可以通过第 1 个操作转换成15，也可以通过第 2 个操作转换成 20，也可以通过第 3 个操作转换成 24。

这里的任务是计算出给定 n 转换成 1 的最少操作步数，也有可能 n 根本无法转换成 1。

Input

第一行仅有一个整数 q (1 ≤ q ≤ 1000)，代表询问数。

接下来 q 行，每行一个正整数 n (1 ≤ n ≤ 10¹⁸) 表示一次询问。

Output

输出 q 行，每行一个整数表示对应的询问的答案。如果 n 确实无法转换成 1，对应答案请输出 -1。

Sample Input

7

1 10 25 30 14 27 1000000000000000000

Sample Output

0

4 6 6 -1 6 72

解题思路

由题知n的三种转换形式，比较得知n/2缩小的速度最快，所以优先判断n是不是偶数，如果是就除以2，若不是就判断是否是3或5的倍数，直到n==1或者n不是2，3，5的倍数退出循环。

若n==1输出次数，n!=1输出-1；

AC代码：

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'typedef long long ll;int main(){
       SIS;    int T;    cin >> T;    while(T--)    {
           ll x,ans=0;        cin >> x;        if(x==1)         {
               cout << 0 << endl;            continue;        }        if(x&1 && x%3!=0 && x%5!=0)        {
               cout << -1 << endl;            continue;        }        while(x!=1)        {
               while(!(x&1)) x>>=1,ans++;            if(x%3==0) x=2*x/3,ans++;            if(x%5==0) x=4*x/5,ans++;            if(x&1 && x%3!=0 && x%5!=0) break;        }        if(x==1) cout << ans << endl;        else cout << -1 << endl;    }    return 0;}
   

转载地址：http://nsyof.baihongyu.com/