题意
如果一个数 $x$ 的约数和 $y$ （不包括他本身）比他本身小，那么 $x$ 可以变成 $y$，$y$ 也可以变成 $x$。例如 $4$ 可以变为 $3$，$1$ 可以变为 $7$。限定所有数字变换在不超过 $n$ 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。
思路
求树的最长链
设$d1[i]$为以$i$为根的子树中，i到叶子节点距离最大值
设$d2[i]$为以$i$为根的子树中，i的叶子节点距离次大值(除了最大值所在的子树)
若j为i的儿子，那么：
- 若$d1[j]+dis[i][j]>d1[i]$，则$d2[i]=d1[i];d1[i]=d2[j]=dis[i][j];$
- 否则，若$d1[j]+dis[i][j]>d2[i]$，则$d2[i]=d1[j]+dis[i][j]; $
最后扫描所有节点，最长链=max{d1[i]+d2[i]}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
#define eps 1e-4
using namespace std;
//priority_queue<int,vector<int>,greater<int> > q1;
//priority_queue<int> q2;
//set<int> s;
//list<int> l;
//map<int> mp;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void write(int zx){
if(zx<0){zx=-zx;putchar('-');}
if(zx<10) putchar(zx+'0');
else{
write(zx/10);
putchar(zx%10+'0');
}
}
int sum[500001],n,d1[500001],d2[500001],ans;
void Pri(){
for(int i=1;i<=n;i++){
for(int j=2;j<=n/i;j++){
if(i*j>n) break;
sum[i*j]+=i;
}
}
}
void dp(){
for(int i=n;i>=1;i--){
if(sum[i]<i){
if(d1[i]+1>d1[sum[i]]){
d2[sum[i]]=d1[sum[i]];
d1[sum[i]]=d1[i]+1;
}else if(d1[i]+1>d2[sum[i]]) d2[sum[i]]=d1[i]+1;
}
}
}
int main(){
n=read();
Pri();
dp();
for(int i=1;i<=n;i++) ans=max(ans,d1[i]+d2[i]);
write(ans);putchar('\n');
return 0;
}
