对于一个正整数x,定义x的“精神值”为小于x的所有x的约数之和。现在请你选出若干个不重复的正整数,这些正整数的和不超过s,使得他们的精神值之和最大。c++代码
时间: 2024-01-22 08:18:58 浏览: 57
抱歉,作为AI语言模型,我只能生成代码,而不能运行代码。以下是一种可能的C++代码实现,仅供参考:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
int T, x, s, cnt, ans;
int fac[MAXN], f[MAXN], pre[MAXN];
int read() {
int x = 0, flag = 1;
char c = getchar();
while (!isdigit(c)) { if (c == '-') flag = -1; c = getchar(); }
while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * flag;
}
void solve() {
T = read();
while (T--) {
cnt = ans = 0;
x = read(), s = read();
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
fac[++cnt] = i;
if (i != x / i) fac[++cnt] = x / i;
}
}
sort(fac + 1, fac + cnt + 1);
for (int i = 1; i <= cnt; i++) {
f[i] = fac[i] - 1;
for (int j = 1; j < i; j++) {
if (fac[i] % fac[j] == 0)
f[i] = max(f[i], f[j] + fac[i] - 1);
}
pre[i] = pre[i - 1] + fac[i];
}
for (int i = 1; i <= cnt; i++) {
if (pre[i] <= s)
ans = max(ans, f[i]);
else
break;
}
printf("%d\n", ans);
}
}
int main() {
solve();
return 0;
}
```
代码思路:
1. 对于每个正整数x,求出其所有约数fac,并将它们存储在数组fac中。为了方便求解,需要保证fac按照升序排序。
2. 定义f[i]表示选择x的精神值为fac[i]时,使得所有精神值之和最大的方案的和。
3. 定义pre[i]表示前i个约数的和。遍历数组fac,并根据动态规划的思想更新f数组的值。
4. 遍历数组fac,若前i个约数的和仍不超过s,则更新ans的值,否则退出循环。
阅读全文