企业官网建设流程全解析

题目描述

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)=75+7+5=87d(75) = 75 + 7 + 5 = 87d(75)=75+7+5=87。从任意正整数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)，其中M=106M = 10^6M=106，完全可以接受。但更常见的做法是采用“筛法”思想：从111到MMM遍历，若当前数尚未被标记为非自数，则它一定是自数，输出它；然后从它开始不断迭代d(x)d(x)d(x)，将生成的所有数标记为非自数，直到超过MMM或遇到已标记的数（避免重复工作）。由于d(x)d(x)d(x)的增长速度至少为111，迭代次数有限，总时间复杂度O(M)O(M)O(M)，非常高效。

解题思路

1. 使用布尔数组number[1000001]，初始全为000（表示未标记，默认为自数候选）。
2. 从i=1i = 1i=1到MMM遍历：
   • 若number[i] == 0，则iii是自数，输出。
   • 然后从iii开始，反复计算next = d(current)，并将number[next]标记为111（表示非自数），直到next > M或number[next]已经被标记（说明后续数已处理过，可提前终止）。
3. 计算d(x)d(x)d(x)时，累加xxx与其各位数字之和。

注意：虽然M=1000000M=1000000M=1000000不是很大，但使用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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intnumber[1000001]={0};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);number[1]=0;for(inti=1;i<=1000000;i++){if(number[i]==0){cout<<i<<'\n';intstart=i;while(start<1000000){intnext=start;while(start>0){next+=start%10;start/=10;}if(next<=1000000){if(number[next]==1)break;number[next]=1;start=next;}elsebreak;}}}return0;}

总结

本题利用筛法思想，通过标记所有非自数，一次性输出所有自数。关键点在于理解自数的定义以及生成元迭代过程，并利用数组标记避免重复计算。由于上限仅为10610^6106，算法效率很高。此方法也适用于寻找更大范围内的自数，只需调整数组大小即可。该题是典型的“生成元”问题，掌握筛法思路对解决类似问题很有帮助。