[BZOJ1263/Luogu4157][SCOI2006]整数划分

题目链接:

BZOJ1263

Luogu4157

严谨的数学结论题!!一眼出结论,秒了

首先,若把(n)分成(m)个数,显然越平均乘积越大(小学奥数可能用不等式证明?)

若分的(m)个数(实数)为(x),然后就有答案方程(f(x)=x^{frac nx}=(x^{frac 1x})^n)

因为方程(f'(x)=x^{frac 1x})(x)(e)时最大

(似乎是某年(PKUSC)数学题?网上应该有详细证明,用的导数?我不会不证明了,反正很显然,取值发现答案在(2sim 3)之间就猜出来了,实在不行可以借助计算机画图Geogebra

又因为这题要取整数,那么就要分成尽可能多的(2)(3)(在(e)附近的正整数)。

那么接着怎么做呢?枚举(2)的个数?

其实(2)的个数取值只可能是({0,1,2})其中一个,因为(2+2+2=3+3,2^3<3^2),所以有(3)(2)就可以换成(2)(3)

然后套高精度即可。

#include <cstdio>

int n;
struct Big
{
	int s[10005],l;
	inline void operator*=(const int x)
	{
		for(int i=l;i>=1;--i)
			s[i+1]+=(s[i]*=x)/10,s[i]%=10;
		for(int i=1;i<=l;++i)
			s[i+1]+=s[i]/10,s[i]%=10;
		if(s[l+1])++l;
	}
}Ans;

int main()
{
	scanf("%d",&n);
	Ans.s[Ans.l=1]=1;
	for(int i=0;i<=2;++i)
		if((n-i*2)%3==0)//可以取i个2
		{
			for(int j=(n-i*2)/3;j;--j)Ans*=3;
			for(int j=i;j;--j)Ans*=2;
		}
	printf("%d
",Ans.l);
	for(int i=Ans.l;i>=1&&Ans.l-i<100;--i)printf("%d",Ans.s[i]);
	putchar('
');
	return 0;
}
原文地址:https://www.cnblogs.com/LanrTabe/p/10211480.html