【紫书】例题3-5 生成元（Digit Generator, ACM/ICPC Seoul 2005, UVa1583）

【题目描述】

如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求最小生成元。无解输出0。例如，n=216，121，2005时的解分别为198，0，1979。

【代码实现】

　　方法1

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n = 0;
 9     while ( scanf ("%d", &n) == 1) {
10         int flag = 1;
11         for ( int i = 1; i <= n; i++ ) {
12             int t = i, sum = 0;
13             while ( t > 0 ) {
14                 sum += t % 10;
15                 t /= 10;
16             }
17 //            printf ("i = %d, sum = %d
", i, sum);
18             if ( i + sum == n ) {
19                 printf ("%d
", i);
20                 flag = 0;
21                 break;
22             }
23         }
24         if ( flag ) printf ("0
");
25     }
26     
27 //    printf ("Time used = %f
", (double)clock() / CLOCKS_PER_SEC);
28      
29     return 0;
30 }

　　方法2

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAX (int)1e5 + 10
 5 
 6 using namespace std;
 7 
 8 int a[MAX];
 9 
10 int main()
11 {
12     for ( int i = 1; i < MAX; i++ ) {
13         int t = i, j = i;
14         while ( t ) {
15             j += t % 10;
16             t /= 10;
17         }
18         if ( a[j] == 0 || a[j] > i ) a[j] = i;
19     }
20     
21      int n = 0;
22      while ( scanf ("%d", &n) == 1 ) printf ("%d
", a[n]);
23      
24     return 0;
25 }

【总结】

自己的方法是纯暴力枚举，真的简单。。但对一个数进行按位拆分的时候写的麻烦了。。明明很久以前就写过的OTL。

作者的方法是，先用一个数组将所有下标对应的最小生成元都存起来，最后输入只要查表即可。比单纯的暴力枚举要高效很多，不必每次输入n都从1~n-1找一遍。妙啊，巧用数组！