Uva1583 Digit Generator解题报告

    这道题很简单，就是求最小生成元。

这道题的生成元是这样定义的： N的生成元为x加上x的各个位置上的数字之和。

N的范围是1到100000

所以我们有两种方法。第一种是打表
代码如下：

#include <stdio.h>
#include <string.h>

#define maxn 100001

int main(void)
{
    int n, t;
    int ans[maxn];
    memset(ans, 0, sizeof(ans));

    int i;
    for(i = 1; i <= maxn; ++i)
    {
        int x = i, y = i;
        while(x)
        {
            y += x % 10;
            x /= 10;
        }
        if(ans[y] == 0 || ans[y] > i) ans[y] = i;
    }

    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}

第二种就是直接来，不打表：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        int digit = 0;
        int t = n;
        while(t)
        {
            ++digit;
            t /= 10;
        }
        int x;
        for(x = n - digit * 9; x < n; ++x)
        {
            int sum = x;
            int temp = x;
            while(temp)
            {
                sum += temp % 10;
                temp /= 10;
            }
            if(sum == n)
            {
                printf("%d\n", x);
                break;
            }
        }
        if(x == n)
            printf("0\n");
    }
    return 0;
}

两种都在UvaOJ上AC了，但是，从速度上来说，打表更快，所以以后做题的时候，如果单次计算量较大，就可以考虑打表。