题目183：整数平分后的最大乘积

欧拉计划

Maximum product of parts


Let 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 = r^k.

For example, if 11 is split into five equal parts, 11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2, then P = 2.2⁵ = 51.53632.

Let M(N) = P_max 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 P_max = (11/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 = r^k。

比如，如果 11 被平分成 5 块的话，11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2，则 P = 2.2⁵ = 51.53632。

对给定的 N，定义 M(N) = P_max。

可以证明，对 N=11 时，把它平分成 4 块，可以得到 P 的最大值 P_max = (11/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) 的值。

jerryxjr1220

1. from math import gcd
   
2. def M(N):
   
3.     k = 2
   
4.     while N/(k+1)*(k/(k+1))**k>1:
   
5.         k += 1
   
6.     return k
   
7. def D(N):
   
8.     n = M(N)//gcd(N, M(N))
   
9.     if n == 2 or n == 5: return N
   
10.     while n % 2 == 0:
    
11.         n//=2
    
12.     while n % 5 == 0:
    
13.         n//=5
    
14.     return N if n==1 else -N
    
15. print(sum([D(i) for i in range(5,10001)]))

复制代码

-48861552
[Finished in 15.2s]
我的结果正好差个负号，不知道是不是N和-N弄反了...

永恒的蓝色梦想

思路：
把 N 平分为 k 份，k=[N/e] 时各部分乘积最大。
M(N)=P_max=(N/k)^k
因为判断分数是否为有限小数，
只需判断分母的因子是否只包括 2 和 5，
且有限小数的幂一定是有限小数，
所以判断 M(N) 是否为有限小数，
只需要判断 k 的因子是否只包括 2 和 5。


代码：
C++ 2ms

1. #include<iostream>
   
2. #include<cmath>
   
3. #include<numbers>
   
4. 
   
5. 
   
6. 
   
7. constexpr int gcd(int a, int b)noexcept {
   
8.     int c = 0;
   
9. 
   
10.     while (b) {
    
11.         c = a % b;
    
12.         a = b;
    
13.         b = c;
    
14.     }
    
15. 
    
16.     return a;
    
17. }
    
18. 
    
19. 
    
20. 
    
21. int main(void) {
    
22.     using namespace std;
    
23.     ios::sync_with_stdio(false);
    
24. 
    
25.     int i, temp, sum = 0;
    
26. 
    
27. 
    
28.     for (i = 5; i <= 10000; i++) {
    
29.         temp = round(i / numbers::e);
    
30.         temp /= gcd(temp, i);
    
31. 
    
32.         while (!(temp & 1)) {
    
33.             temp >>= 1;
    
34.         }
    
35.         while (!(temp % 5)) {
    
36.             temp /= 5;
    
37.         }
    
38. 
    
39.         if (temp == 1) {
    
40.             sum -= i;
    
41.         }
    
42.         else {
    
43.             sum += i;
    
44.         }
    
45.     }
    
46. 
    
47. 
    
48.     cout << sum << endl;
    
49.     return 0;
    
50. }

复制代码

瓦屋青衣

1. import time
   
2. import math
   
3. 
   
4. timeStart = time.time()
   
5. 
   
6. n = 10000
   
7. 
   
8. def gcd(x:int, y:int) -> int:
   
9.     while True:
   
10.         r = x%y
    
11.         if r == 0:
    
12.             return y
    
13.         else:
    
14.             x, y = y, r
    
15. 
    
16. def d(n:int) -> int:
    
17.     x = n / math.e
    
18.     x1 = int(x)
    
19.     x2 = int(x+1)
    
20.     x = x1 if x1*math.log(n/x1) > x2*math.log(n/x2) else x2
    
21.     x /= gcd(n, x)
    
22. 
    
23.     while x%2==0:
    
24.         x //= 2
    
25.     while x%5 == 0:
    
26.         x //= 5
    
27. 
    
28.     return n if x != 1 else -n
    
29. 
    
30. ans = sum(d(x) for x in range(5, n+1))
    
31. 
    
32. print(ans)
    
33. 
    
34. print(f'time used: {time.time() - timeStart: .3f} s')

复制代码

代码比2楼要长，但时间要少得多