题解 P1900 【自我数】

题目描述-->[p1900 自我数](https://www.luogu.org/problemnew/show/P1900) ## 本文转自[@keambar](https://www.cnblogs.com/keam37/p/3815306.htm) ### 转载已经原作者同意 **分析：** 思路还是比较好给出的： 用类似筛选素数的方法筛选自我数。 但是要注意到题目限制的空间仅有4M,不够开10^7 那么大的数组. 于是进一步分析问题我们发现每一次拓展出来的数最多比原数大63！ 这是由于最多不过7位数,假设每一位都是9的话,拓展出来的数才大 7*9=63. 所以我们，对拓展出来的数取模，再用数组存下来。 至于输出自我数,经过测试. 在SGU的数据里自我数的答案没有超过10^6 刚好用掉4M的空间 ⊙﹏⊙b汗 最保险的方法还是仅将需要的自我数号码存下来, 排序后用二分查找判断当前找到的数是否是需要存下的. 最后再将存下的数按照读入的顺序输出. **原作者代码**↓ ```cpp #include<cstdio> int n, m, k; bool pd[100]; int f[1000000], tol; int Find (int x) { for (k = 0; x != 0; x /= 10) k += x % 10; return k; } void init() { int i, j; tol = 0, j = 0; for (i = 1; i <= n; i++) { if (!pd[i % 100]) f[++tol] = i; else pd[i % 100] = false; //这里用了个小技巧，大大减少取模的次数，很容易想明白 if (i % 10 == 0) j = i + Find (i); else j += 2; pd[j % 100] = true; } } int main() { scanf ("%d%d", &n, &m); init(); printf ("%d\n", tol); for (int i = 1; i <= m; i++) { scanf ("%d", &k); printf ("%d ", f[k]); } return 0; } ``` 本人辣鸡代码就不放了emmm 应原作者要求:本题亦可以在**SGU**上找到 //不过,我没有找到链接 emm