题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1128
暴力即可,不过这里先开始我给TLE了,因为我把每一个数,都从他的d(n), d(d(n))…都算了,遍历从1~1000000 =。=
其实再想想,只需要算d(n)即可,然后遍历1~1000000,因为比如d(…d(n))是x,则d(x)任然会在后面遍历到。。。
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | // Author: Tanky Woo // Blog: www.WuTianQi.com // Title: HDOJ 1128 Self Numbers // About: #include <iostream> #include <string> #include <map> #include <algorithm> using namespace std; bool hash[1000005]; int t1, t2; /* inline void fun(int n) { while(n <= 1000000) { t1 = n; t2 = n; while(t1) { t2 += t1%10; t1 /= 10; } n = t2; hash[n] = 1; } } */ inline void fun(int n) { t1 = n; t2 = n; while(t1) { t2 += t1%10; t1 /= 10; } n = t2; hash[n] = 1; } int main() { memset(hash, 0, sizeof(hash)); for(int i=1; i<= 1000000; ++i) fun(i); for(int i=1; i<=1000000; ++i) if(hash[i] == 0) printf("%d\n", i); return 0; } |