洛谷P1925 最大划分乘积的数学解法

题目

题解

这道题用到一点导数和数论的知识，很容易看出这道题是求函数

\[f(x)=(\frac{n}{x})^{x}
\]

（ \(x\) 为正整数）的最大值。我们可以对 \(ln(f(x))\) 进行求导，求出 \(ln(f(x))\) 的最大值。

\[ln(f(x))=x(lnn-lnx)
\]

\[(ln(f(x)))'=lnn-lnx-1
\]

\(ln(f(x))\) 的最大值必然在 \(\lfloor \frac{n}{x} \rfloor\) 和 \(\lceil \frac{n}{x} \rceil\) 中取得。所以只需将这两个值代入取较大值即可。

对于两数相除是否为有限小数,只需将 \(x\) 除以 \(\gcd(n,x)\) 之后，再判断其能否表示为 \(2^{p_{1}}\times 5^{p_{2}}\ (p_{1}\in N,p_{2}\in N)\) ，能表示则代表其为有限小数。

代码

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

const double e = exp(1.000);

int gcd(int a, int b)

{

	return (b == 0) ? a : gcd(b, a % b);

}

double cc(int n, int x)

{

	return (double)x * log((double)n / x);

}

int calc(int n)

{

	int x1 = n / e, x2 = n / e + 1;

	int x = cc(n, x1) > cc(n, x2) ? x1 : x2;

	int p = gcd(n, x);

	x /= p;

	while (x % 2 == 0)

		x /= 2;

	while (x % 5 == 0)

		x /= 5;

	return (x == 1) ? -n : n;

}

int main()

{

	int a;

	cin >> a;

	int res = 0;

	for (int i = 5; i <= a; i++)

		res += calc(i);

	cout << res;

	return 0;

}

巴特西

洛谷P1925 最大划分乘积的数学解法

题目

题解

代码

最新文章

热门文章