Luogu P1925 最大划分乘积

题意

略。

题解

简单题。

容易看出 (f(x)=left(dfrac{n}{x} ight)^x)，考虑求这个东西的极值，看一眼发现是取对数求导法，那么有

所以

于是

考虑求导数的零点。注意到 (f(x)=left(dfrac{n}{x} ight)^x) 没有零点，所以零点只可能存在于右边的括号中，也即 (x=dfrac{n}{e})。

由于最终的 (x) 只能取整数，所以极值只可能在 (leftlfloordfrac{n}{e} ight floor) 或 (leftlceildfrac{n}{e} ight ceil) 取到，比较两个值可以直接比较对数大小。接下来就很平凡了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
typedef long double db;
const ll MAXN=2e5+51;
const db E=exp(1.0);
ll n,res,lx,rx,g;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline db lnf(ll n,ll x)
{
    return log(1.0L*n)*x-log(1.0L*x)*x;
}
inline ll calc(ll n)
{
    lx=n/E,rx=n/E+1,lx=lnf(n,lx)>lnf(n,rx)?lx:rx,g=__gcd(n,lx),lx/=g;
    while(lx%2==0)
    {
        lx/=2;
    }
    while(lx%5==0)
    {
        lx/=5;
    }
    return lx==1?-n:n;
}
int main()
{
    n=read();
    for(register int i=5;i<=n;i++)
    {
        res+=calc(i);
    }
    printf("%d
",res);
}