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

欧拉计划 · 发表于 2016-10-4 00:40:24

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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 · 发表于 2017-9-21 17:37:08

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([D(i) for i in range(5,10001)]))

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

永恒的蓝色梦想 · 发表于 2020-4-29 09:53:27

本帖最后由永恒的蓝色梦想于 2021-2-18 21:25 编辑

思路：
把 N 平分为 k 份，k=[N/e] 时各部分乘积最大。
M(N)=P_max=(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;
}

瓦屋青衣 · 发表于 2021-3-30 23:51:13

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楼要长，但时间要少得多

账号		自动登录	找回密码
密码			立即注册