题目描述
如果 x 加上 x 的各个数字之和得到 y, 就说 x 是 y 的生成元给出 n(1n100000), 求最小生成元无解输出 0 例如, n=216,121,2005 时的解分别为 198,0,1979
代码实现
方法 1
- #include < iostream > #include < cstdio > using namespace std;
- int main() {
- int n = 0;
- while (scanf("%d", &n) == 1) {
- int flag = 1;
- for (int i = 1; i <= n; i++) {
- int t = i,
- sum = 0;
- while (t > 0) {
- sum += t % 10;
- t /= 10;
- }
- // printf ("i = %d, sum = %d\n", i, sum);
- if (i + sum == n) {
- printf("%d\n", i);
- flag = 0;
- break;
- }
- }
- if (flag) printf("0\n");
- }
- // printf ("Time used = %f\n", (double)clock() / CLOCKS_PER_SEC);
- return 0;
- }
方法 2
- #include < stdio.h > #include < string.h >
- #define MAX(int) 1e5 + 10
- using namespace std;
- int a[MAX];
- int main() {
- for (int i = 1; i < MAX; i++) {
- int t = i,
- j = i;
- while (t) {
- j += t % 10;
- t /= 10;
- }
- if (a[j] == 0 || a[j] > i) a[j] = i;
- }
- int n = 0;
- while (scanf("%d", &n) == 1) printf("%d\n", a[n]);
- return 0;
- }
总结
自己的方法是纯暴力枚举, 真的简单但对一个数进行按位拆分的时候写的麻烦了明明很久以前就写过的 OTL
作者的方法是, 先用一个数组将所有下标对应的最小生成元都存起来, 最后输入只要查表即可比单纯的暴力枚举要高效很多, 不必每次输入 n 都从 1~n-1 找一遍妙啊, 巧用数组!
来源: http://www.bubuko.com/infodetail-2499260.html