题解 P1734 【最大约数和】

其实这题是个背包（我用暴力只得了20分） S就是背包容量V，i就是重量，i的因子和就是价值。 这样一讲公式就出来了吧！ 公式： ```cpp i为第一个数，j为第二个数，a[k]为k的因子和 dp[i]=max(dp[i-j]+a[j],dp[i]); ``` 这个公式我想大家都能很方便地推出来。 接下来我要讲一讲本题一个很重要的优化，楼下们的代码中都或多或少的有，只是他们没有解释（大佬哪有时间解释） 于是，我这个蒟蒻就来解释一下吧！ 本题一个很重要的优化就是：预处理！ ```cpp void prime(){ for (int i=1;i<=n;i++) for (int j=i*2;j<=n;j+=i)a[j]+=i; } ``` 看到这段预处理代码，有没有想到筛法？ 没错，就是从筛法改过来的！ 这个是筛法↓ ```cpp bool s[10000]={1,1};//0和1啥都不是，定1！ int a[10000],ps;//a数组存最后的质数，ps为这个数组的下标 //全局数组初值全为0 inline void $(){//不要在意函数名，这只是个筛法函数 //财迷心窍的我 for (int j=2;j<10000;j++)//暴力！汗！ if (!s[j]){//s[j]=0，表明j不是合数（合数为1） a[ps++]=j;//纪录下j这个质数，下一个 for (int k=j*2;k<10000;k+=j)//k=j*2省一个判断，每次+j，保证是j的倍数 s[k]=1;//既然是j的倍数，那一定是合数，标记！ } } ``` 我将筛法改了一下，就有了这个函数。 因为是要因子和，而合数因子也算在里面，所以不用判断质数，那个bool数组自然就不要了 j=i\*2表示j初值为i的2倍，j+=i则保证j是i的倍数，就加上i这个因子 开始预处理到n，打好了一个动态表，接下来dp时就可以直接引用了 筛法的应用还有很多，所以，随机应变，打动态表可以节省很多时间哦！ 代码我就不贴了，希望大家能明白预处理的重要性