线性筛+背包

讲道理这道题在线性筛后就让我们想到暴力的做法，毕竟写了\(n \leq 1000\)。

其实你要用背包做的。

dp也很显然的，就用一维来表示和不超过\(i\)的最大的所谓约数和。

为什么是所谓的呢？你约数和是包括自己的。所以在这道题中你要自己把数字本身手工去掉。

当然不是叫你在线性筛的时候弄掉，在dp的时候抠掉即可。

线性筛不难的，就那么几种情况，手工推推式子就可以得到了。

讲道理这题还pj-

代码：

#include
    
     #include
     
      const int maxn = 1005, N = maxn - 5;bool notprime[maxn];int prime[maxn], tot;int ysh[maxn], mm[maxn];int dp[maxn];int n;void init(){    notprime[1] = true; ysh[1] = 1; mm[1] = 1;    for(int i = 2; i <= N; i++)    {        if(!notprime[i])        {            prime[++tot] = i;            ysh[i] = mm[i] = i + 1;        }        for(int j = 1; j <= tot && i * prime[j] <= N; j++)        {            notprime[i * prime[j]] = true;            if(i % prime[j])            {                ysh[i * prime[j]] = ysh[i] * ysh[prime[j]];                mm[i * prime[j]] = prime[j] + 1;            }            else            {                ysh[i * prime[j]] = ysh[i] / mm[i] * (mm[i] * prime[j] + 1);                mm[i * prime[j]] = mm[i] * prime[j] + 1;                break;            }        }    }}int main(){    init();    scanf("%d", &n);    for(int i = 1; i <= n; i++)    {        dp[i] = ysh[i] - i;        for(int j = 1; j < i; j++)        {            dp[i] = std::max(dp[i], dp[j] + ysh[i - j] - (i - j));        }    }    //for(int i = 1; i <= n; i++) printf("%d ", dp[i]);    //printf("\n");    printf("%d\n", dp[n]);    return 0;}