UVa 640 Selft Numbers-北京尧图网络

题目描述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算法效率很高。此方法也适用于寻找更大范围内的自数只需调整数组大小即可。该题是典型的“生成元”问题掌握筛法思路对解决类似问题很有帮助。

UVa 640 Selft Numbers

相关推荐

让大模型生成可维护代码：约束式 Prompt 工程的设计与验证

深度解析DDS在ROS2核心技术中的关键作用

云原生网络之Cilium的eBPF数据面

更多资讯

PLC工程师必读：IEC 61131标准与五种编程语言实战解析

Mininet三种创建方式：可视化拖拽、命令行速建与交互式调试

DNS 劫持检测接口接入教程：domain 参数、请求示例与风险分级解读

银行卡识别接口接入教程：参数、请求示例与返回字段解读

企业供应商项目接口接入教程：参数、请求示例与分页返回解读

MCP 鉴权凭证生命周期管理：基于短期动态 Token 与细粒度访问控制的隔离实战

今日更新

MATLAB缩进快捷键与批量格式化实战指南

用Poco实现Qt风格信号与槽的跨平台C++方案

ESXi裸机虚拟化安装指南：从硬件兼容到虚拟机部署

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？