蓝桥杯 adv205 拿糖果

蓝桥杯 adv205 拿糖果

问题描述

妈妈给小B买了N块糖!但是她不允许小B直接吃掉。

假设当前有M块糖,小B每次可以拿P块糖,其中P是M的一个不大于根号下M的质因数。这时,妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。

现在小B希望知道最多可以拿多少糖。

输入格式

一个整数 N

输出格式

最多可以拿多少糖

样例输入

15

样例输出

6

数据规模和约定

N <= 100000

参考解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int main() {
int n;
cin >> n;

int tmp[100001], dp[100001];
vector<int> prim;
memset(tmp, 1, sizeof(tmp));

for (int i = 2; i < 350; ++i) { // 350 sqrt(100001)的估计
if (!tmp[i]) continue;
for (int j = i * i; j < 100001; j+=i)
tmp[j] = 0;
prim.push_back(i);
}

for (int i = 1; i <= n; ++i) {
for (int j = 0; j < prim.size(); ++j) {
if (prim[j] > sqrt(i)) break;
if (i % prim[j] == 0)
dp[i] = max(dp[i], dp[i-2*(prim[j])] + prim[j]);
}
}
cout << dp[n];
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×