原题题面

读入一个正整数$n$（$10\le n\le 31000$）。要求将$n$写成若干个正整数之和，并且使这些正整数的乘积最大。

例如，$n=13$，则当n表示为$4+3+3+3$（或$2+2+3+3+3$）时，乘积=$108$为最大。

输入格式

只有一个正整数$n$（$10\le n\le 31000$）

输出格式

第1行输出一个整数，为最大乘积的位数。 第2行输出最大乘积的前100位，如果不足100位，则按实际位数输出最大乘积。 （提示：在给定的范围内，最大乘积的位数不超过5000位）。

输入样例

13

输出样例

3 108

题面分析

简单概括一下就是:已知$\sum x_i=N$，求$max\{\prod x_i\}$. 看到$\sum x_i$和$\prod x_i$很容易 就能想到均值不等式。 假设$x_i$有$n$项，我们有 $$(\frac{\sum x_i}{n}{)}^n\ge \prod x_i$$ 因为取到等号时，$x_i$两两相等，因此$x_i$要取的尽量平均，于是问题变成了求出 $(\frac{\sum x_i}{n}{)}^n=(\frac{N}{n}{)}^n$的最大值 我们可以用一些高数知识对它进行处理 记$y=(\frac{N}{n}{)}^n$,两边套$In$，得到$Iny=nInN-nInn$ 两边再求导，得到$$\frac{y^{\prime }}{y}=InN-Inn-1$$(这里不再赘述为什么左边不是$\frac{1}{y}$) 移项得到$$y^{\prime }=(InN-Inn-1)\ast (\frac{N}{n}{)}^n$$ 令$y^{\prime }=0$，即$$(InN-Inn-1)\ast (\frac{N}{n}{)}^n=0$$ 因为$(\frac{N}{n}{)}^n$必定大于0，故原式等价于求$(InN-Inn-1)=0$，易知$n=\frac{N}{e}$ 即把每个数尽可能地分成e。 且$y$在$(0,\frac{N}{e}]$上单调递增,$[\frac{N}{e},\infty )$上单调递减。 但考虑到在整数范围，$\frac{N}{e}$取不到，因此候选项有$\frac{N}{2},\frac{N}{3}$两个数，于是问题就转化为哪个优先取的问题。 代入方程，得到$2^{\frac{N}{2}}<3^{\frac{N}{3}}$ 如何证明？ 两边取对数得到$\frac{N}{2}In2和\frac{N}{3}In3$ 注意到$\frac{In2}{2}<\frac{In3}{3}$ 故$2^{\frac{N}{2}}<3^{\frac{N}{3}}$, 故优先取3，然后取2。 证毕。 于是这就变成了憨憨题，我们根据$nmod3$的不同结果来讨论取的方法。 $nmod3=0$时，无脑拿3,答案就是$3^{\frac{N}{3}}$ $nmod3=1$时，拿出一个3变两个2,答案就是$3^{\frac{N-1}{3}-1}\ast 2^2$ $nmod3=2$时，拿一个2之后全变3,答案就是$3^{\frac{N-2}{3}}\ast 2$

AC代码(70ms)

import java.math.BigInteger; import java.util.Scanner; import static java.lang.Math.min; /** * @author DrGilbert */ public class Main { public static void main (String[] args) { Scanner cin = new Scanner (System.in); int n; while(cin.hasNext ()) { n=cin.nextInt (); BigInteger ans; 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 { ans=BigInteger.valueOf (3).pow ((n/3)).multiply (BigInteger.valueOf (2)); } String ans1=ans.toString (); System.out.println (ans1.length ()); for(int i=0;i<min(100,ans1.length ());i++) { System.out.print (ans1.charAt (i)); } System.out.println (); } } }

后记

用什么FFT，大数他不够香吗 DrGilbert 2020.10.4