题目183：整数平分后的最大乘积
Maximum product of partsLet N be a positive integer and let N be split into k equal parts, r = N/k, so that N = r + r + ... + r.
Let P be the product of these parts, P = r × r × ... × r = rk.
For example, if 11 is split into five equal parts, 11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2, then P = 2.25 = 51.53632.
Let M(N) = Pmax for a given value of N.
It turns out that the maximum for N = 11 is found by splitting eleven into four equal parts which leads to Pmax = (11/4)4; that is, M(11) = 14641/256 = 57.19140625, which is a terminating decimal.
However, for N = 8 the maximum is achieved by splitting it into three equal parts, so M(8) = 512/27, which is a non-terminating decimal.
Let D(N) = N if M(N) is a non-terminating decimal and D(N) = -N if M(N) is a terminating decimal.
For example, ΣD(N) for 5 ≤ N ≤ 100 is 2438.
Find ΣD(N) for 5 ≤ N ≤ 10000.
题目：
N 是一个正整数，然后，将 N 平分成 k 份，r = N/k，则 N = r + r + ... + r。
定义 P 为这些的乘积，即 P = r × r × ... × r = rk。
比如，如果 11 被平分成 5 块的话，11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2，则 P = 2.25 = 51.53632。
对给定的 N，定义 M(N) = Pmax。
可以证明，对 N=11 时，把它平分成 4 块，可以得到 P 的最大值 Pmax = (11/4)4；也就是说，M(11) = 14641/256 = 57.19140625，是个有限小数。
至于 N=8 时，则是把 8 分成 3 部分时取到 P 的最大值，得到 M(8) = 512/27，这是个无限小数。
如果 M(N) 是无限小数，则定义 D(N) = N ，否则，D(N) = -N。
例如，对于 5 ≤ N ≤ 100 来说， ΣD(N) 是 2438。
请给出 5 ≤ N ≤ 10000 时，ΣD(N) 的值。
from math import gcd
def M(N):
k = 2
while N/(k+1)*(k/(k+1))**k>1:
k += 1
return k
def D(N):
n = M(N)//gcd(N, M(N))
if n == 2 or n == 5: return N
while n % 2 == 0:
n//=2
while n % 5 == 0:
n//=5
return N if n==1 else -N
print(sum())
-48861552
我的结果正好差个负号，不知道是不是N和-N弄反了... 本帖最后由 永恒的蓝色梦想 于 2021-2-18 21:25 编辑
思路：
把 N 平分为 k 份，k= 时各部分乘积最大。
M(N)=Pmax=(N/k)k
因为判断分数是否为有限小数，
只需判断分母的因子是否只包括 2 和 5，
且有限小数的幂一定是有限小数，
所以判断 M(N) 是否为有限小数，
只需要判断 k 的因子是否只包括 2 和 5。
代码：
C++ 2ms#include<iostream>
#include<cmath>
#include<numbers>
constexpr int gcd(int a, int b)noexcept {
int c = 0;
while (b) {
c = a % b;
a = b;
b = c;
}
return a;
}
int main(void) {
using namespace std;
ios::sync_with_stdio(false);
int i, temp, sum = 0;
for (i = 5; i <= 10000; i++) {
temp = round(i / numbers::e);
temp /= gcd(temp, i);
while (!(temp & 1)) {
temp >>= 1;
}
while (!(temp % 5)) {
temp /= 5;
}
if (temp == 1) {
sum -= i;
}
else {
sum += i;
}
}
cout << sum << endl;
return 0;
} import time
import math
timeStart = time.time()
n = 10000
def gcd(x:int, y:int) -> int:
while True:
r = x%y
if r == 0:
return y
else:
x, y = y, r
def d(n:int) -> int:
x = n / math.e
x1 = int(x)
x2 = int(x+1)
x = x1 if x1*math.log(n/x1) > x2*math.log(n/x2) else x2
x /= gcd(n, x)
while x%2==0:
x //= 2
while x%5 == 0:
x //= 5
return n if x != 1 else -n
ans = sum(d(x) for x in range(5, n+1))
print(ans)
print(f'time used: {time.time() - timeStart: .3f} s')
代码比2楼要长，但时间要少得多
页:
[1]