C++14(g++5.4) 解法, 执行用时: 75ms, 内存消耗: 24824K, 提交时间: 2020-01-10 10:51:53

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std; 
const int N = 1e6+6;
int n; 
vector<int> edge[N];
int d1[N], d2[N];

int getVal(int x) {
	int res = 1;
	for (int i = 2; i*i <= x; ++i)
		if (x%i == 0) {
			res += i;
			if (x/i != i)
				res += x/i;
		} return res;
}

void dp (int u) {
	for (int i=0, v; i < edge[u].size(); ++i) {
		dp(v = edge[u][i]);
		if (d1[v]+1 > d1[u]) d2[u] = d1[u], d1[u] = d1[v]+1;
		else d2[u] = std::max(d2[u], d1[v]+1);	
	}
}

int main() {
	scanf("%d", &n);
	for (int i=1, t; i <= n; ++i)
		if ((t=getVal(i)) < i)
			edge[t].push_back(i);
			
	dp(1);
	
	int res = 0;
	for (int i = 1; i <= n; ++i)
		res = std::max(res, d1[i]+d2[i]);
	printf("%d", res);
	return 0;
}

C++(clang++11) 解法, 执行用时: 17ms, 内存消耗: 888K, 提交时间: 2021-04-24 06:02:21

#include <iostream>
using namespace std;
int sum[50001],n,d1[50001],d2[50001];
void dp()
{
	int i;
	for (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()
{
	int i,j,ans=0;
	cin>>n;
	for (i=1;i<=n;i++)
	  for (j=2;j<=n/i;j++)
	    sum[i*j]+=i;
	dp();
	for (i=1;i<=n;i++)
	  if (d1[i]+d2[i]>ans) ans=d1[i]+d2[i];
	cout<<ans;
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 792K, 提交时间: 2023-08-05 08:59:46

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 50005;
int n, ans = 0, s[N], f[N];
int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) 
        for (int j = i * 2; j <= n; j += i)
            s[j] += i;

    for (int i = n; i; i--) {
        if(s[i] >= i) continue;
        ans = max(ans, f[s[i]] + f[i] + 1);
        f[s[i]] = max(f[s[i]], f[i] + 1);
    }
    printf("%d\n", ans);
    return 0;
}