题目大意描述:
题目:固执的数??持久的数??
2014/12/06 18:41
数字乘法的持久性由 Neil Sloane定义, (Neil Sloane在一个娱乐杂志上发表关于数字持久性的文章 6, 1973, pp. 97-98., 1973),这个数经过一些步骤变成一位数反复的乘上这个数字(那个数字啊???不明白),例如
679 -> 378 -> 168 -> 48 -> 32 -> 6.(没有看懂啊)
就是说679的持久性是6,一位数持久性的结果是0,现在它是已知的有数字是11的持久性,目前尚且不知道什么是12的持久性,但是我们知道如果他们存在,那么位数至少会超过3000位。
这里需要你解决的问题是,什么是最小的数字这样计算的第一步,它的持久性结果在给定的数字?(好吧,看明白了,每一位数字之积,寻找等于这个数的最小的那个数字吧)没组测试数据输入一个不超过1000位的数字。
应该就是从最大的9开始除,一直除到1,如果最后的结果大于9那么就是不存在的了。算是贪心吧,毕竟是从最大的数字开始。可以看做是一耳光高精度运算,简单的除法。
试写代码吧。
算是1A吧,不过感觉代码写的好烂啊,不忍直视
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 1005
int OK, K, c[maxn];
int a[maxn];
void chu(int b[], int i, int n, int p)
{
    int j, yu=0;
    if(i==n && (b[i]==1||b[i]==0))return ;
    if(p == 1)
    {
        OK = 0;
        return ;
    }
    for(j=i; j<=n; j++)
        c[j] = b[j];
    for(j=i; j<=n; j++)
    {
        c[j] += yu * 10;
        yu = c[j] % p;
        c[j] /= p;
    }
    if(yu == 0)
    {
        a[K++] = p;
        for(j=i; c[j] == 0 && j<=n; j++);
        i=j;
        for(; j<=n; j++)
            b[j] = c[j];
        chu(b, i, n, p);
    }
    else
        chu(b, i, n, p-1);
}
int main()
{
    char s[maxn];
    while(scanf("%s", s), strcmp(s ,"-1"))
    {
        int i, n=strlen(s), b[maxn]={0};
        for(i=0; i<n; i++)
            b[i] = s[i] - '0';
        OK = 1, K=0;
        chu(b, 0, n-1, 9);
        if(n==1)
            printf("1%s\n", s);
        else if(OK)
        {
            sort(a, a+K);
            for(i=0; i<K; i++)
                printf("%d", a[i]);
            printf("\n");
        }
        else
            printf("There is no such number.\n");
    }
    return 0;
}
05-11 01:11