\(f(i)\)表示对于i块糖的所有拿法,存储最大糖数目
\(f(i) = max\{f(i - 2 * j) + j\}\), 其中\(j\)为\(i\)的所有满足小于等于\(\sqrt{i}\)质因数
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int f[N];
int main(){
cin >> n;
for(int i = 4; i <= n; i ++){
int t = i;
for(int j = 2; j <= t / j; j ++){
if(t % j == 0){
while(t % j == 0) t /= j;
f[i] = max(f[i], f[i - 2 * j] + j);
}
}
}
cout << f[n] << endl;
return 0;
}