Persistent Numbers（贪心+高精度）

Persistent Numbers（贪心+高精度）

Persistent Numbers

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit  ​​Status​​​  ​​​Practice​​​  ​​​POJ 2325​​

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

描述: 给定一个整数M，求一个最小的整数N满足N每位数的乘积等于M。（M的位数不超过1000）

若不存在这样的整数N，则输出"There is no such number.",最后以输入M=-1结束；

思路:贪心+高精度

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

实现代码:

#include#define N 1010char a[N];int z[8];int length;bool div(int d){ int z=0; int j=0; char tmp[N]; for(int i=0;i1;i--) { z[i-2]=0; while(div(i))z[i-2]++; } if(length!=1) { printf("There is no such number.\n"); continue; } for(int i=2;i<10;i++) { while(z[i-2]) { printf("%d",i); z[i-2]--; } } printf("\n"); } return 0;}

Persistent Numbers

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit  ​​Status​​​  ​​​Practice​​​  ​​​POJ 2325​​

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。