题目描述194919491949年印度数学家D.R. Kaprekar\texttt{D.R. Kaprekar}D.R. Kaprekar发现了一类被称为“自数”self-number\texttt{self-number}self-number的数。对于任意正整数nnn定义d(n)nd(n) nd(n)n加上nnn的各位数字之和。例如d(75)757587d(75) 75 7 5 87d(75)757587。从任意正整数nnn出发可以构造无限递增序列n,d(n),d(d(n)),…n, d(n), d(d(n)), \ldotsn,d(n),d(d(n)),…例如从333333开始得到33,39,51,57,69,…33, 39, 51, 57, 69, \ldots33,39,51,57,69,…。若存在某个nnn使得d(n)md(n) md(n)m则称nnn是mmm的一个生成元。一个数如果没有生成元则称为自数。例如101101101有两个生成元919191和100100100。小于100100100的自数有131313个1,3,5,7,9,20,31,42,53,64,75,86,971, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 971,3,5,7,9,20,31,42,53,64,75,86,97。本题要求输出所有不超过100000010000001000000的正整数自数按升序排列每行一个。输入格式本题没有输入。输出格式输出所有不超过100000010000001000000的自数每行一个整数按升序排列。样例输出1 3 5 7 9 20 31 42 53 64 ... 9903 9914 9925 9927 9938 9949 9960 9971 9982 9993 ...题目分析本题要求找出111到100000010000001000000之间的所有自数。直接对每个数检查是否存在生成元复杂度为O(Mlog⁡M)O(M \log M)O(MlogM)其中M106M 10^6M106完全可以接受。但更常见的做法是采用“筛法”思想从111到MMM遍历若当前数尚未被标记为非自数则它一定是自数输出它然后从它开始不断迭代d(x)d(x)d(x)将生成的所有数标记为非自数直到超过MMM或遇到已标记的数避免重复工作。由于d(x)d(x)d(x)的增长速度至少为111迭代次数有限总时间复杂度O(M)O(M)O(M)非常高效。解题思路使用布尔数组number[1000001]初始全为000表示未标记默认为自数候选。从i1i 1i1到MMM遍历若number[i] 0则iii是自数输出。然后从iii开始反复计算next d(current)并将number[next]标记为111表示非自数直到next M或number[next]已经被标记说明后续数已处理过可提前终止。计算d(x)d(x)d(x)时累加xxx与其各位数字之和。注意虽然M1000000M1000000M1000000不是很大但使用while迭代比直接对每个数检查生成元更快。复杂度分析每个数最多被标记一次每次迭代计算数字和的时间与位数相关最多777位总操作数约为O(M⋅log⁡M)O(M \cdot \log M)O(M⋅logM)但实际接近O(M)O(M)O(M)。空间复杂度O(M)O(M)O(M)。代码实现// Self Numbers// UVa ID: 640// Verdict: Accepted// Submission Date: 2016-08-23// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intnumber[1000001]{0};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);number[1]0;for(inti1;i1000000;i){if(number[i]0){couti\n;intstarti;while(start1000000){intnextstart;while(start0){nextstart%10;start/10;}if(next1000000){if(number[next]1)break;number[next]1;startnext;}elsebreak;}}}return0;}总结本题利用筛法思想通过标记所有非自数一次性输出所有自数。关键点在于理解自数的定义以及生成元迭代过程并利用数组标记避免重复计算。由于上限仅为10610^6106算法效率很高。此方法也适用于寻找更大范围内的自数只需调整数组大小即可。该题是典型的“生成元”问题掌握筛法思路对解决类似问题很有帮助。