数字转换

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1619 字
对每个数x，若其真因子和y<x，则x与y可互
一本通
例
正文

/*
原题：数字转换（一本通 5.2 例3）
题意：对每个数 x，若其真因子和 y<x，则 x 与 y 可互变；求在不超过 n 的正整数里最长变换步数。
思路：以 x->y(y<x) 建森林（每个点至多一条向更小的边），答案即整片森林的最长路径（直径）长度。
复杂度：O(n log n) 求因子和 + O(n) 求直径；空间 O(n)。
易错点：变换只能在正整数范围内，y 必须 ≥1；最长路径用两次 BFS。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=50005;
vector<int> g[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> d(n+1,0);
    for(int i=1;i<=n/2;i++)
        for(int j=i*2;j<=n;j+=i) d[j]+=i;
    for(int i=1;i<=n;i++)
        if(d[i]<i&&d[i]>=1){
            g[i].push_back(d[i]);
            g[d[i]].push_back(i);
        }
    vector<int> dist(n+1,-1);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(dist[i]<0){
            queue<int> q;
            q.push(i);
            dist[i]=0;
            int far=i;
            while(!q.empty()){
                int u=q.front();q.pop();
                for(int v:g[u])
                    if(dist[v]<0){
                        dist[v]=dist[u]+1;
                        q.push(v);
                        if(dist[v]>dist[far])far=v;
                    }
            }
            for(int j=1;j<=n;j++)dist[j]=-1;
            q.push(far);
            dist[far]=0;
            int far2=far;
            while(!q.empty()){
                int u=q.front();q.pop();
                for(int v:g[u])
                    if(dist[v]<0){
                        dist[v]=dist[u]+1;
                        q.push(v);
                        if(dist[v]>dist[far2])far2=v;
                    }
            }
            ans=max(ans,dist[far2]);
        }
    }
    cout<<ans<<"\n";
    return 0;
}
数字转换

正文

一本通·提高篇的其它内容
