欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

OJ 1451 数字游戏

程序员文章站 2022-03-23 15:34:52
描述给定一个整数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。否则,打印所需的最小步数。...

描述

给定一个整数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

相关标签: OJ c++