如果x加上x的各個數字之和得到y，就說x是y的生成元。
給出n（1≤n≤100000），求最小生成元。
無解輸出0。
例如，n=216，121，2005時的解分別為198，0，1979。

我的思路很簡單，就是枚舉，每輸入一個數n就從1到n-1開始枚舉，代碼如下。

#include<stdio.h>
#include<iostream>
#include<String.h>using namespace std;
int sum(int n)// 求n加上n的各個數字之和 
{int s = 0, n1 = n;while(n1 != 0){s += n1%10;n1 /= 10;}return s+n; 
}
int main()
{int n,i ;while(1){scanf("%d", &n);for(i=0; i<n; i++){if(sum(i) == n){printf("%d\n", i);break;}}if(i == n) printf("%d\n", 0);}
} 

但是這種做法需要每次計算n-1次，因此可以考慮建一個10000長度的表，存每個數的最小生成元，每次輸入n直接從表中查。

#include<stdio.h>
#include<iostream>
#include<String.h>#define MAXN 100000
using namespace std;
int ans[MAXN] = {0};int main()
{int n,i ;for(i = 1; i <= MAXN; i++){int x = i, y = i;while(x > 0) { y += x % 10; x /= 10;} //求i和i每位的和 if(ans[y] == 0 || i < ans[y]) ans[y] = i;//注意是“最小”生成元 }while(1){cin >> n;cout << ans[n] << endl;}
}