Round757 Div2 D2

题目描述

给定序列，合理安排顺序，最大化， ，。

解题思路

我们考虑将每一个数放在一个图中。设某一个点上的数为，连接。

每个点的最大的答案贡献为，其中表示的是以为因数的所有的个数。

本题的关键在于计算。我们从图论的角度来看，从到之间有两条路径，一条是先经过再经过，另一条是先经过再经过。如果直接计数会导致重复。

我们强制每一个答案的提交一定按照单调递增的路径来进行。实现如下：

for (int i = 1; i <= prime_cnt; ++i) {
  for (int j = maxn / prime[i]; j >= 1; --j) {
    cnt[j] += cnt[j * prime[i]];
  }
}