POJ 1316 - Self Numbers

http://poj.org/problem?id=1316

概要

d(n) を「n 自身と，n を十進表記したときの各位の和」と定義する．

m = d(n) に対して，n を m の generator とする． 例えば d(91) = 101 なので，99 は 101 の generator であり，また d(100) = 101 なので 100 も 101 の generator である．

どの数の generator でもない数を self-number という． 例えば 1 は self-number である．

10000 以下のすべての self-number を昇順に答える．

解法

やるだけ．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int f(int n)
 5 {
 6   int x = n;
 7   while (n > 0) {
 8     x += n % 10;
 9     n /= 10;
10   }
11   return x;
12 }
13 
14 int main()
15 {
16   static const int M = 10000;
17   static bool a[M];
18   for (int i = 1; i <= M; i++) {
19     const int d = f(i);
20     if (d <= M) {
21       a[d-1] = true;
22     }
23   }
24   for (int i = 0; i < M; i++) {
25     if (!a[i]) {
26       printf("%d\n", i+1);
27     }
28   }
29   return 0;
30 }