Poj 2325 Persistent Numbers——（高精度除法+贪心）

69 阅读 0 评论 46 点赞

我是靠谱客的博主彩色音响，这篇文章主要介绍Poj 2325 Persistent Numbers——（高精度除法+贪心），现在分享给大家，希望可以做个参考。

Persistent Numbers

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
14
17
29
77
There is no such number.
2688

题意： 给你个数，这个数通过每位数的相乘得到另一个数，持续这个过程，直到得到一个一位数，例如：233=233=18，18=18=8，8就是最后的这个数，现在知道最后这个数，让你计算出最小的上一位数，例如18是29得到，所以最小就是29；给出的数字最大可达1000位（1亿是9位数）。

题解： 这里我们要用到大数的除法。举个例子介绍一下大数除法：

比如 524134 除以 123。结果是4261

第一位4的来源是我们把 524和123对齐，然后进行循环减法，循环了4次，余32，将32134的前三位321继续和123对齐，循环减法2次，余75，把7534的前三位753和123对齐，循环减法6次，余15，将154和123对齐，只能减1次，所以结果是4 2 6 1。(524134不能整除123）

把上述过程程序化

把A,B两个数存入char数组 0下标表示的是最高位
把A的前lenB位z(取A的前 B的位数)和B对齐进行大小比较
如果 2. 的比较结果里A的前lenB位大,那么就进行循环减法,直到它比B小,循环的次数记作s[0]表示最终结果的最高位
如果2的比较结果里A的前lenB位小,什么也不做.
把B整体向后以一位,和A的最高位对齐(最高位可能暂时是0) 把s的下标迭代+1 表示进行下一位的计算
不断地比较,直到当B的尾部和A的尾部对齐时,说明A的最后lenB位也进行了循环减法算数,所以得到了结果.终止程序
//以上提到的lenB都是最开始的B的长度,后来由于移位会导致增大

以上来自这儿

解释一下代码：
这里从9 开始遍历，我们先找出这个数的最大的因子把它尽可能的放到低位（先放个位，再放十位……）因为这样算出来的这个数才是最小的（才符合题目要求），然后输出的时候从2开始遍历（求因子和输出因子遍历顺序是相反的）输出，最终得到的也就是最小的结果。

复制代码

1
2
3
4
5
6
for(int i=9;i>1;i--)
{
	factor[i-2] = 0;
	while(div(i)) factor[i-2]++;    // 如果i能被我们输入的数整除，说明i是输入的数的一个因子，记录
}

c++ AC 代码

复制代码

#include<cstdio>
#define N 1010
char number[N];
int factor[9];
int length;

bool div(int d)   // 大数除法
{
    int last = 0,j=0;
    char tmp[N];
    for(int i=0;i<length;i++)
    {
        int x = number[i] + last*10;
        int y = x / d;
        last = x % d;
        if(y || j) tmp[j++] = y;
    }
    if (last) return false;
    for(int i=0;i<j;i++) number[i] = tmp[i];
    length = j;
    
    return true;
}

int main()
{
    while(scanf("%s",number) && !(number[0]=='-' && number[1]=='1' && number[2]==''))
    {
        for(length=0;number[length];length++)
            number[length] -= '0';
        
        if(length==1)   // 如果输入的数字只有一位的话那么它的最小的构成的数就是 1*该数 --> 答案就是 1*10 + 该数
        {
            printf("1%dn",number[0]);
            continue;
        }

// 因数从2-9进行判断（1 就不要判断了，1乘以任何数都是1）这里是倒序判断
        for(int i=9;i>1;i--)
        {
            factor[i-2] = 0;
            while(div(i)) factor[i-2]++;    // 如果i能被我们输入的数整除，说明i是输入的数的一个因子，记录
        }

if (length!=1)     // 无解的情况
        {
            printf("There is no such number.n");
            continue;
        }

for (int i = 2; i < 10; i++)        // 顺序输出我们输入的数的因子
        {
            while(factor[i-2])
            {
                printf("%d",i);
                factor[i-2]--;
            }
        }
        printf("n");
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#define N 1010
char number[N];
int factor[9];
int length;

bool div(int d)   // 大数除法
{
    int last = 0,j=0;
    char tmp[N];
    for(int i=0;i<length;i++)
    {
        int x = number[i] + last*10;
        int y = x / d;
        last = x % d;
        if(y || j) tmp[j++] = y;
    }
    if (last) return false;
    for(int i=0;i<j;i++) number[i] = tmp[i];
    length = j;
    
    return true;
}

int main()
{
    while(scanf("%s",number) && !(number[0]=='-' && number[1]=='1' && number[2]==''))
    {
        for(length=0;number[length];length++)
            number[length] -= '0';
        
        if(length==1)   // 如果输入的数字只有一位的话那么它的最小的构成的数就是 1*该数 --> 答案就是 1*10 + 该数
        {
            printf("1%dn",number[0]);
            continue;
        }


        // 因数从2-9进行判断（1 就不要判断了，1乘以任何数都是1）这里是倒序判断
        for(int i=9;i>1;i--)
        {
            factor[i-2] = 0;
            while(div(i)) factor[i-2]++;    // 如果i能被我们输入的数整除，说明i是输入的数的一个因子，记录
        }

        if (length!=1)     // 无解的情况
        {
            printf("There is no such number.n");
            continue;
        }

        for (int i = 2; i < 10; i++)        // 顺序输出我们输入的数的因子
        {
            while(factor[i-2])
            {
                printf("%d",i);
                factor[i-2]--;
            }
        }
        printf("n");
    }
    return 0;
}

附python代码（不知道能不能过（毕竟人家不支持python这种赖皮语言））：
如果是python选手就很舒服了，因为python里面的input和print是支持大数输入和输出的，python里面的大数运算也不会有精度的损失，用python写这个代码要简单很多。（不是很建议使用eval()）除法那里要用 ”//“ 来整除，用 ”/“ 除出来是浮点数如果数字太大会报 ”OverflowError: integer division result too large for a float“ 的错误。（不要问我怎么知道的，手动狗头）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def main():

    while 1:
        res = []
        a = eval(input())
        if int(a) == -1: break

        if a<10 and a>=0:
            print('1{}'.format(a))
            continue
        
        for i in range(9,1,-1):
            while not a%i:
                res.append(str(i))
                a //= i      // 用”//“ 来整除 这样除出来还是整型
                if a <= 9:
                    res.append(str(a))
                    a = 0
                    break
            if not a:
                break

        if not res or len(res)==1 or a:
            print('There is no such number')
        else:
            res.reverse()
            print(''.join(res))
main()