当前位置:首页 » Project Euler » 详细页

Maximum product of parts 题号:183 难度: 45 中英对照

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 = 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.

Solution

对于数$n$,拆分数量为$k$,则$P=\left( \frac{n}{k} \right)^k$。 则: $$ln P=k(ln n-ln k)$$ 对$k$求导有: $$\frac{p'}{p}=ln n-ln k -1$$ 令之为$0$,有: $k=\frac{n}{e}$ 因为$k$是整数,所以$P$的极大值点在$max\left( P\left( \left[ \frac{n}{e} \right] \right), P\left( \left[ \frac{n}{e} \right] +1\right) \right)$取到。 注意判定$\frac{p}{q}$是否为有限小数,只需要利用java.math.BigDecimal.divide函数的特性即可。

Code

import java.math.BigDecimal;

public final class p183 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    static public String run() {
    	int res=0;
		for (int n = 5; n <= 10000; n++)
			res+=solve(n);
		return ""+res;
	}
    
    static int solve(int n){
    	int x1=(int)(n/Math.E);
    	int x2=x1+1;
    	double lnp1=x1*(Math.log(n)-Math.log(x1));
    	double lnp2=x2*(Math.log(n)-Math.log(x2));
    	int ans=x1;
    	if(Double.compare(lnp1,lnp2)<0) ans=x2;
    	try{
    		BigDecimal.valueOf(n).divide(BigDecimal.valueOf(ans));
    		return -n;
    	}catch(ArithmeticException e){
    		return n;
    	}
    }
    
    
}
48861552
89ms