UVa 547 DDF

题目描述题目定义了一种数列十进制数字因子数列DDF\texttt{DDF}DDF从任意大于111的整数x1x_1x1​开始xi1x_{i1}xi1​等于xix_ixi​的所有正因子的各位数字之和。已知该数列最终会进入循环最终稳定在一个数。给定区间[m,n][m, n][m,n]m,n≤3000m, n \le 3000m,n≤3000要求找出该区间内起始数生成的DDF\texttt{DDF}DDF中最长的一个即数列长度最大。若长度相同取起始数最小的。输出该数列。输入格式输入包含多行每行两个整数mmm和nnn表示区间范围。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个区间输出两行第一行Inputi: m n第二行Outputi: 数列数列中的数用空格分隔。样例输入200 500 100 150输出Input1: 200 500 Output1: 285 66 36 46 18 30 27 22 9 13 5 6 12 19 11 3 4 7 8 15 Input2: 100 150 Output2: 102 36 46 18 30 27 22 9 13 5 6 12 19 11 3 4 7 8 15题目分析本题的核心是预计算每个数的下一个数然后找到最长链。预计算对于111到300030003000的每个数计算其所有正因子的各位数字之和得到下一个数。由于数列最终会重复可以使用动态规划或记忆化搜索计算每个数开始的链长。链长计算若已知next[i]\textit{next}[i]next[i]则链长len[i]1len[next[i]]\textit{len}[i] 1 \textit{len}[\textit{next}[i]]len[i]1len[next[i]]递归。由于最终会进入循环需要避免无限递归可以使用记忆化搜索。查找最长链对于区间内的每个数找出链长最大的数若长度相同取起始数最小。输出从该数开始输出整个链直到进入循环注意循环部分只输出一次。复杂度分析预计算O(3000×3000)O(3000 \times \sqrt{3000})O(3000×3000​)查询O(n)O(n)O(n)。代码实现// DDF// UVa ID: 547// Verdict: Accepted// Submission Date: 2016-08-18// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intdigit_sum[3100],next_number[3100],length[3100]{0};intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);for(inti1;i3000;i){intdigit0,ti;while(t){digitt%10;t/10;}digit_sum[i]digit;}for(inti1;i3000;i){intnext0;for(intj1;jsqrt(i);j){if((i%j)0){intbi/j;nextdigit_sum[j];if(b!j)nextdigit_sum[b];}}next_number[i]next;}for(inti1;i3000;i){if(length[next_number[i]]0)length[i]1length[next_number[i]];else{intstep1,starti;while(next_number[start]!start){step;startnext_number[start];}length[i]step;}}intm,n,cases0;while(cinmn){cases;coutInputcases: m n\n;intstartmin(m,n),endmax(m,n),max_i,max_length0;for(intistart;iend;i)if(length[i]max_length){max_ii;max_lengthlength[i];}coutOutputcases: max_i;while(next_number[max_i]!max_i){max_inext_number[max_i];cout max_i;}cout\n;}return0;}