P4157[SCOI2006]整数划分

P4157 [SCOI2006]整数划分 数学推导 + 大数

题意思路Code（67MS）

传送门：https://www.luogu.com.cn/problem/P4157

借鉴大佬：https://blog.csdn.net/oampamp1/article/details/108919448

题意

给一个整数N，将他拆成若干整数，求他们乘积最大值。

思路

$先将题目转化一下：$

$$已知\sum _{i=1}^n{x}_i=N，求max\{\prod _{i=1}^n{x}_i\}(n表示x_i有几项)$$

$首先根据均值不等式（调和\le 几何\le 算术\le 平方）：$ $$\frac{n}{{\sum }_{i=1}^n\frac{1}{x_i}}\le \sqrt[n]{\prod _{i=1}^n{x}_i}\le \frac{{\sum }_{i=1}^n{x}_i}{n}\le \sqrt[n]{\frac{{\sum }_{i=1}^n{x}_i^2}{n}}$$

$所以可以得到：$ $$\frac{{\sum }_{i=1}^n{x}_i}{n}\ge \sqrt[n]{\prod _{i=1}^n{x}_i}$$

$${\left(\frac{{\sum }_{i=1}^n{x}_i}{n}\right)}^n\ge \prod _{i=1}^n{x}_i$$

$观察上式，要使乘积最大，那需要尽量取等号，所以x_i要尽量平均，所以得到下式：$

$${\left(\frac{N}{n}\right)}^n=\prod _{i=1}^n{x}_i$$

$令y=(\frac{N}{n}{)}^n，两边同时取对数得：$

$$\ln y=n\ln N-n\ln n$$

$两边同时对n求导得：$

$$\frac{y^{\prime }}{y}=\ln N-lnn-1$$

$$得y^{\prime }=(\ln N-\ln n-1)(\frac{N}{n}{)}^n$$

$令y^{\prime }=0，因为(\frac{N}{n}{)}^n>0，所以\ln N-\ln n-1=0，即：$

$$n=e^{\ln N-1}=\frac{N}{e}$$

$由于n是在整数域里，所以n只有两个选择\frac{N}{2}和\frac{N}{3}，那么该取哪一个呢？$

$刚开始的{\prod }_{i=1}^n{x}_i=(\frac{N}{n}{)}^n=2^{\frac{N}{2}}或3^{\frac{N}{3}}，现在就看哪个大。$

$根据上图可知，2^{\frac{N}{2}}<3^{\frac{N}{3}},当然也可以手动算一下。$

$所以得{\prod }_{i=1}^n{x}_i=3^{\frac{N}{3}}最大，即优先取3，没有3取2，总之，推导到最后就是个憨憨题。总结一下：$

$让Nmod3:$

$-Nmod3=0，全部拆成3，ans=3^{\frac{N}{3}}$ $-Nmod3=1，拿出一个3然后加1组成4，其他都为3，ans=3^{\frac{N-1}{3}-1}\ast 4$ $-Nmod3=2，拿出一2，其他都为3，ans=3^{\frac{N-2}{3}}\ast 2$

$由于答案爆longlong，所以用JAVA大数，这不比高精度香吗？$

Code（67MS）

import java.util.*; import java.math.*; import static java.lang.Math.min; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); int N; N = in.nextInt(); BigInteger ans = new BigInteger("1"); if(N % 3 == 0) { ans = BigInteger.valueOf(3).pow((N / 3)); } else if(N % 3 == 1) { ans = BigInteger.valueOf(3).pow((N / 3 - 1)).multiply(BigInteger.valueOf(4)); } else if(N % 3 == 2) { ans = BigInteger.valueOf(3).pow((N / 3)).multiply(BigInteger.valueOf(2)); } String s = ans.toString(); System.out.println(s.length()); for(int i = 0;i < min(100, s.length()); i++) { System.out.print(s.charAt(i)); } System.out.println(); } }