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
|
#include <iostream> #include <cstdlib> #include <cstring> #include <queue> #include <algorithm> #define MAXN 50007 using namespace std;
int head[MAXN],ver[MAXN<<2],nxt[MAXN<<2],tot=0; int n,root,maxdep,d[MAXN]; bool v[MAXN]; queue<int> q;
inline void (int x,int y){ ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; }
inline int sum(int x){ int res=1; for(int i=2;i<=(int)(x/i);++i){ if(x%i==0) res+=(i+(x/i)); if(i*i==x) res-=i; } return res; }
inline void bfs(int s){ memset(v,0,sizeof(v)); memset(d,0,sizeof(d)); maxdep=0; v[s]=1;d[s]=1; q.push(s); while(q.size()>0){ int x=q.front();q.pop(); for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(v[y]) continue; v[y]=1; d[y]=d[x]+1; if(d[y]>maxdep){maxdep=d[y];root=y;} q.push(y); } } }
inline void init(){ scanf("%d",&n); for(int i=1;i<=n;++i){ int y=sum(i); if(y<i){ add(i,y),add(y,i); } } bfs(1); bfs(root); printf("%dn",maxdep-1); }
int main(){ init(); return 0; }
|
近期评论