选取和不超过 S 的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大
时间: 2024-02-12 15:06:46 浏览: 32
我们可以先考虑如何计算一个正整数的约数之和。设 $n$ 是一个正整数,$d$ 是 $n$ 的一个约数,则 $n/d$ 也是 $n$ 的一个约数。因此,我们可以将 $n$ 的所有约数分成两组:小于 $\sqrt{n}$ 的约数和大于 $\sqrt{n}$ 的约数。对于小于 $\sqrt{n}$ 的约数 $d$,可以求出 $n/d$,然后将它们的和累加起来;对于大于 $\sqrt{n}$ 的约数 $d$,可以求出 $d$,然后将它们的和累加起来。这样就可以计算出 $n$ 的约数之和。
接下来,我们考虑如何选取若干个不同的正整数,使得它们的和不超过 $S$,并且它们的约数之和最大。我们可以使用动态规划来解决这个问题。
设 $f(i, j)$ 表示选取前 $i$ 个不同的正整数,它们的和不超过 $j$,并且它们的约数之和最大的值。则对于第 $i$ 个正整数,它可以选也可以不选。如果它不选,那么 $f(i,j) = f(i-1,j)$;如果它选,则 $f(i,j)$ 的值为前 $i-1$ 个正整数中,和不超过 $j-i$ 的所有方案中,约数之和最大的方案再加上第 $i$ 个正整数的约数之和。因此,可以得到状态转移方程:
$$f(i,j) = \max(f(i-1,j), f(i-1,j-i) + \sigma(i))$$
其中,$\sigma(i)$ 表示第 $i$ 个正整数的约数之和。初始状态为 $f(0,j) = 0$(选取 0 个正整数),$f(i,0) = 0$(和为 0)。
最终的答案为 $f(n,S)$。时间复杂度为 $O(nS\sqrt{S})$。
代码实现如下:
```python
def divisor_sum(n):
"""
计算 n 的约数之和
"""
s = 0
for i in range(1, int(n**0.5)+1):
if n % i == 0:
s += i
if i != 1 and i**2 != n:
s += n // i
return s
def max_divisor_sum(n, S):
"""
选取和不超过 S 的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大
"""
f = [[0] * (S+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, S+1):
f[i][j] = f[i-1][j]
if j >= i:
f[i][j] = max(f[i][j], f[i-1][j-i] + divisor_sum(i))
return f[n][S]
```
其中,n 和 S 分别为题目中的两个参数,返回值为所有数的约数之和的最大值。