生成元（Digit Generator, AMC/ICPC Seoul 2005, UVa1583）

标签（空格分隔）： c

---

题目

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

分析

假设所求的生成元为 m。可以知道 m < n。尝试枚举所有的 m < n，取出是 n 的生成元，没有则为 0。

已知 198 是 216 的生成元，计算公式如下：

   198= 198 + 1 + 9 + 8= 216

解题

第一种：

#include <stdio.h>
#include <string.h>
#define maxn 100005int ans[maxn];int main() {int T, n;memset(ans, 0, sizeof(ans));for (int m = 0; m < 217; m++) {int x = m, y = m;while (x > 0) {y += x % 10;x /= 10;}printf("x = %d, y = %d\n", x, y);if (ans[y] == 0 || m < ans[y]) {ans[y] = m;printf("ans[y] = %d\n", ans[y]);      }}scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d\n", ans[n]);}return 0;
}

第二种：

#include <stdio.h>int main() {int i = 0, n;scanf("%d", &n);if (n >= 1 && n <= 100000) {for (;;) {if (i == 100001) {printf("%d\n", 0);break;}i++;int x = i, y = i;while (x > 0) {y += x % 10;x /= 10;}if (y == n) {printf("%d\n", i);break;}}}return 0;
}