POJ2325 Persistent Numbers(大数+贪心)

发布时间：2020-12-14 03:26:00 所属栏目：大数据来源：网络整理

导读：题目： Persistent Numbers Time Limit: ? 1000MS ? Memory Limit: ? 65536K Total Submissions: ? 3698 ? Accepted: ? 1740 Description The multiplicative persistence of a number is defined by Neil Sloane (Neil J.A. Sloane in The Persistence of a

题目：

Persistent Numbers

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?3698	?	Accepted:?1740

Description

The multiplicative persistence of a number is defined by Neil Sloane (Neil J.A. Sloane in The Persistence of a Number published in Journal of Recreational Mathematics 6,1973,pp. 97-98.,1973) as the number of steps to reach a one-digit number when repeatedly multiplying the digits. Example: ?

679 -> 378 -> 168 -> 48 -> 32 -> 6.

That is,the persistence of 679 is 6. The persistence of a single digit number is 0. At the time of this writing it is known that there are numbers with the persistence of 11. It is not known whether there are numbers with the persistence of 12 but it is known that if they exists then the smallest of them would have more than 3000 digits. ?
The problem that you are to solve here is: what is the smallest number such that the first step of computing its persistence results in the given number?

Input

For each test case there is a single line of input containing a decimal number with up to 1000 digits. A line containing -1 follows the last test case.

Output

For each test case you are to output one line containing one integer number satisfying the condition stated above or a statement saying that there is no such number in the format shown below.

Sample Input

Sample Output

10
11
14
17
29
77
There is no such number.
2688

Source

Waterloo local 2003.07.05

[Submit]?? [Go Back]?? [Status]?? [Discuss]

思路：

csdn抽风。。一直发不上去

给了一个大整数n，然后求一个整数，要求这个整数的各个位数的乘积为这个数
从9开始依次递减，用这个数整数，最后把得到的字符串倒过来就行
这里要用到大数运算，直接套模板

代码：

#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<iostream>
#include <cmath>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the fuck!!!")
#define N (1010)
#define ll long long
using namespace std;
string div(string str,int x)
{
    string ans="";
    int len=str.length();
    int y=0;
    for(int i=0; i<len; i++)
    {
        ans+=char((y*10+(str[i]-'0'))/x+'0');
        y=(y*10+(str[i]-'0'))%x;
    }
    while(*(ans.begin())=='0'&&ans.size()>1)
        ans.erase(ans.begin());

    if(y)ans=str;
    return ans;
}
int main()
{
    string s;
    while(cin>>s)
    {
        if(s=="-1")return 0;
        if(s.length()==1)
            cout<<"1"<<s<<endl;
        else
        {
            string ans="",ss=s;//ss是原字符串的复制
            for(int i=9; i>0; i--)
            {
                while(ss.length()!=1)//判断一个数字能不能连续除
                {
                    string qq=div(ss,i);//临时保存计算结果
                    if(qq==ss)//当有余数的时候
                        break;
                    else
                    {
                        ans+=(i+'0');
                        ss=qq;
                    }
                }
            }
            if(ss.length()==1)
            {
                ans+=ss;
                reverse(ans.begin(),ans.end());
                cout<<ans<<endl;
            }
            else
                puts("There is no such number.");
        }
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!