poj-2325-Persistent Numbers

￡神魔★判官ぃ 2022-05-20 06:49 131阅读 0赞

Persistent Numbers

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;3957</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;1862</td> 
  </tr> 
 </tbody> 
</table>

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

0
    1
    4
    7
    18
    49
    51
    768
    -1

Sample Output

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

Source

[Waterloo local 2003.07.05][]

题目大意：给你个数，这个数通过每位数的相乘得到另一个数，持续这个过程，直到得到一个一位数，例如：233=2\*3\*3=18，18=1\*8=8，8就是最后的这个数，现在知道最后这个数，让你计算出最小的上一位数，例如18是2\*9得到，所以最小就是29；

思路：由于位数过大，所以选择用字符串输入，并将其转化为数字存进数组，然后从9到2，一个个的找，这里用到[高精度除法][Link 1]，然后判断剩余字符串长度，并倒序输出

代码：

#include<map>
    #include<stack>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define maxn 1100
    #define ll long long
    char s[maxn];
    int l,a[101010],b[101010],z[101010];
    int f(int k)
    {
        int i,j=0,sum=0,x,y=0;
        for(i=0;i<l;i++)
        {
            sum=a[i]+y*10;//本位加上一位未除尽的数的余数
            x=sum/k;
            y=sum%k;
            if(x!=0||j!=0)
            {
                b[j++]=x;
            }
        }
        if(y==0)
        {
            for(i=0;i<j;i++)
                a[i]=b[i];
            l=j;
            return 1;
        }
        else
            return 0;
    }
    int main()
    {
        while(scanf("%s",s)!=EOF)
        {
            l=strlen(s);
            int i,j=0,k;
            if(l==2&&s[0]=='-'&&s[1]=='1')
                break;
           else if(l==1)
           {
               printf("1%s\n",s);
           }
           else
           {
               for(i=0;i<l;i++)
               {
                   a[i]=s[i]-48;
               }
               k=9;
               while(k>=2)
               {
                   if(f(k)!=0)
                   {
                       z[j++]=k;
                   }
                   else
                   {
                       k--;
                   }
               }
               if(l==1)
               {
                   for(i=j-1;i>=0;i--)
                    printf("%d",z[i]);
                   printf("\n");
               }
               else
                printf("There is no such number.\n");
           }
        }
        return 0;
    }

[Waterloo local 2003.07.05]: http://poj.org/searchproblem?field=source&key=Waterloo+local+2003.07.05
[Link 1]: https://baike.baidu.com/item/%E9%AB%98%E7%B2%BE%E5%BA%A6%E7%AE%97%E6%B3%95/1024900#3