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

問題：

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

思路：因為沒有提示資訊，一開始以為一次隻會給出一個輸入，實際上系統先給出輸入的個數cnt，然後在依次給出cnt個輸入。個人采用簡單暴曆的方式，實際上周遊範圍不應該是[1, 100000]。分析可知，輸出ans應該小于輸入n，是以ans最大為n - 1；另外，若n的位數為len，那麼ans位數最多為len，ans的各個數字之和最大為9 * len，是以ans最小為n - 9 * len；周遊範圍為[n - 9 * len, n - 1]；

給出的參考代碼先計算并存儲了[1, 100005]的最小生成元，實際上按照m從小到大的周遊順序，m < ans[y]的情況根本不存在，是以可以去掉這個判斷條件。

 個人代碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int cnt, n, i;
    cin >> cnt;
    while(cnt--)
    {
        cin >> n;
        //求n的位數
        stringstream ss;
        string str;
        ss << n;
        ss >> str;
        int len = (int)str.size();
        for (i = n - 9 * len; i < n; ++i)
        {
            int t = i, sum = i;
            while(t)
            {
                sum += t % 10;
                t /= 10;
            }
            if (sum == n)
            {
                cout << i << endl;
                break;
            }
        }
        if (i == n)
            cout << "0" << endl;
    }
    return 0;
}
           

參考代碼：

#include<stdio.h>
#include<string.h>
#define maxn 100005
int ans[maxn];

int main() {
  int T, n;
  memset(ans, 0, sizeof(ans));
  for(int m = 1; m < maxn; m++) {
    int x = m, y = m;
    while(x > 0) { y += x % 10; x /= 10; }
    if(ans[y] == 0 || m < ans[y]) ans[y] = m;
  }
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &n);
    printf("%d\n", ans[n]);
  }
  return 0;
}