算法提高课汇总

算法思路

模型抽象

对于每个数$x$, 其约数之和$y$只有一个. 若$x\gt y$, 可以认为$y$向$x$连一条边 — $y$看作
是$x$的唯一父节点, 则题目可抽象为若干棵树.

问题转化为在所有 树中求直径 的最大值.

约数之和的计算

• 从定义出发, 对于$x$, 对$1\sim \sqrt{x}$通过试除法求$x$约数之和, 时间复杂度$O(n\sqrt{n})$.

• 类似素数筛法思路, 对于$x$, 枚举其在$1\sim n$中的倍数(根据题意不包括自身), 让其倍数的约数
  之和加上$x$. 时间复杂度$n + \frac{n}{2} + \frac{n}{3} + …$, 调和级数, $n\rightarrow \infty$时接近为$\lg(n) + c$, 所以
  时间复杂度为$O(n\lg(n))$.

具体实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010, M = N;

int n, ans;
int h[N], e[M], ne[M], idx;
int sum[N]; //sum[x]: x的约数之和
bool st[N]; //st[u] = false: u为某棵树的树根

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++ ;
}

int dfs(int u)
{
    int d1 = 0, d2 = 0;
    for ( int i = h[u]; ~i; i = ne[i] )
    {
        int v = e[i];
        int d = dfs(v) + 1; //w[i] = 1
        if ( d >= d1 )  d2 = d1, d1 = d;
        else if ( d > d2 )  d2 = d;
    }
    ans = max(ans, d1 + d2);
    return d1;
}

int main()
{
    cin >> n;
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 2; j <= n / i; j ++ )
            sum[i * j] += i;

    memset(h, -1, sizeof h);
    for ( int i = 2; i <= n; i ++ )
        if ( i > sum[i] )
        {
            add(sum[i], i);
            st[i] = true;
        }

    for ( int i = 1; i <= n; i ++ )
        if ( !st[i] )
            dfs(i);
    cout << ans << endl;

    return 0;
}