UVa 547 DDF

题目描述

题目定义了一种数列（十进制数字因子数列，DDF\texttt{DDF}DDF）：从任意大于111的整数x1x_1x1​开始，xi+1x_{i+1}xi+1​等于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]=1+len[next[i]]\textit{len}[i] = 1 + \textit{len}[\textit{next}[i]]len[i]=1+len[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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;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(inti=1;i<=3000;i++){intdigit=0,t=i;while(t){digit+=t%10;t/=10;}digit_sum[i]=digit;}for(inti=1;i<=3000;i++){intnext=0;for(intj=1;j<=sqrt(i);j++){if((i%j)==0){intb=i/j;next+=digit_sum[j];if(b!=j)next+=digit_sum[b];}}next_number[i]=next;}for(inti=1;i<=3000;i++){if(length[next_number[i]]>0)length[i]=1+length[next_number[i]];else{intstep=1,start=i;while(next_number[start]!=start){step++;start=next_number[start];}length[i]=step;}}intm,n,cases=0;while(cin>>m>>n){cases++;cout<<"Input"<<cases<<": "<<m<<' '<<n<<'\n';intstart=min(m,n),end=max(m,n),max_i,max_length=0;for(inti=start;i<=end;i++)if(length[i]>max_length){max_i=i;max_length=length[i];}cout<<"Output"<<cases<<": "<<max_i;while(next_number[max_i]!=max_i){max_i=next_number[max_i];cout<<' '<<max_i;}cout<<'\n';}return0;}