OJ 1451 数字游戏

描述

给定一个整数n。

您可以使用这个数字执行以下任意操作(可能是零)次数:

如果n能被2整除，则用n/2代替n;

如果n能被3整除，则用2n/3代替n;

如果n能被5整除，就用4n/5代替n。

例如，可以使用第一个操作将30替换为15，使用第二个操作将30替换为20，或者使用第三个操作将30替换为24。

你的任务是找出从n中得到1所需的最小步数，或者说这是不可能做到的。

您必须回答独立于q的查询。

在新行中打印每个查询的答案。如果无法从n中得到1，则打印-1。否则，打印所需的最小步数。

输入
输入的第一行包含一个整数q(1≤q≤1000)——查询的数量。

接下来的q行包含查询。对于每个查询，都有一个整数n(1≤n≤1018)。

输出
每行中打印每个查询的答案。如果无法从n中得到1，则打印-1。否则，打印所需的最小步数。
数字游戏
描述

给定一个整数n。

您可以使用这个数字执行以下任意操作(可能是零)次数:

如果n能被2整除，则用n/2代替n;

如果n能被3整除，则用2n/3代替n;

如果n能被5整除，就用4n/5代替n。

例如，可以使用第一个操作将30替换为15，使用第二个操作将30替换为20，或者使用第三个操作将30替换为24。

你的任务是找出从n中得到1所需的最小步数，或者说这是不可能做到的。

您必须回答独立于q的查询。

在新行中打印每个查询的答案。如果无法从n中得到1，则打印-1。否则，打印所需的最小步数。

输入
输入的第一行包含一个整数q(1≤q≤1000)——查询的数量。

接下来的q行包含查询。对于每个查询，都有一个整数n(1≤n≤1018)。

输出
每行中打印每个查询的答案。如果无法从n中得到1，则打印-1。否则，打印所需的最小步数。

输入样例 1 

7
1
10
25
30
14
27
1000000000000000000
输出样例 1

0
4
6
6
-1
6
72

题目要求通过各种运算最后使数据变为1，如果一个数经历的多次变化之后成为一个不能被2，3，5整除的数那么这个数据就不能变成1，否则为了步数可能的少，那么削减也要和尽可能大，削减从小到大为1/2，2/3，4/5，然后利用这个规律类推即可。

#include <iostream>

using namespace std;
long long MIN;
void doit (long long a,int cont)
{
    if(a%2==0)
    {
        if(a/2==1)
        {
            if(MIN>cont)
                MIN=cont;
        }
        else
            doit(a/2,cont+1);
    }
    else if(a%3==0)
    {
        if(2*a/3==1)
        {
            if(MIN>cont)
                MIN=cont;
        }
        else
            doit(2*a/3,cont+1);
    }
   else if(a%5==0)
    {
        if(4*a/5==1)
        {
            if(MIN>cont)
                MIN=cont;
        }
        else
            doit(4*a/5,cont+1);
    }
    else
        MIN=-1;

}
int main()
{
    long long n,a;
    while(cin>>n)
    {
        while(n--)
        {
            MIN=0x3f3f3f;
            cin>>a;
            if(a==1)
                cout<<"0"<<endl;
            else
            {
                doit(a,1);
                cout<<MIN<<endl;
            }

        }
    }
    return 0;
}

 

本文地址：https://blog.csdn.net/qq_45703684/article/details/107895932