传送门：QAQQAQ
题意：如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y>x且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。
思路：YY一下，若$x$可以变为$y$，则$y$也一定能变为$x$，所以我们对于可以互相变换的点建一条无向边，因为每一个点最多之和一个值比它小的点连边，所以不可能出现环（这点可以人工YY证明）
所以我们在这个无环“森林”中跑一个最长链即可
代码：（其实以1为根跑直径不够严谨，用DP算最长链更好）
#include<bits/stdc++.h> using namespace std; vector<int> v[50005]; int d[50005]; void dfs(int u,int f,int depth) { d[u]=depth; for(int i=0;i<(int)v[u].size();i++) { if(v[u][i]==f) continue; dfs(v[u][i],u,depth+1); } } void init(int n) { for(int i=2;i<=n;i++) { int sum=0; for(int j=1;j*j<=i;j++) { if(i%j==0) { sum+=j; if(j*j!=i&&j!=1) sum+=i/j; } } if(sum<i) { v[sum].push_back(i); v[i].push_back(sum); } } // for(int i=1;i<=n;i++) // { // cout<<i<<":"; // for(int j=0;j<v[i].size();j++) cout<<v[i][j]<<" "; // cout<<endl; // } } int main() { int n; cin>>n; init(n); dfs(1,-1,0); int s=-1,maxn=-1; for(int i=1;i<=n;i++) { if(maxn<d[i]) { maxn=d[i]; s=i; } } dfs(s,-1,0); for(int i=1;i<=n;i++) { if(maxn<d[i]) maxn=d[i]; } cout<<maxn<<endl; return 0; }
原文：https://www.cnblogs.com/Forever-666/p/11279755.html
