自动搬运

查看原文

来自洛谷，原作者为

	Great_Influence **

搬运于2025-08-24 21:31:58，当前版本为作者最后更新于2017-12-10 19:51:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

高中数学题。

首先，对于固定的数字$N$，可以得到$M$关于划分块数$k$的函数$f(k)=M_N(k)=(\frac{N}{k})^k$。然后开始求导。

对两边同时取对数，得

$Ln[f(x)]=xLn[Nx^{-1}]$

求导，得

$\frac{f^\prime(x)}{f(x)}$

$=Ln(\frac{N}{x})+\frac{-Nx}{x^2}*\frac{x}{N}$

$=Ln(\frac{N}{x})-1$

$=Ln(\frac{N}{ex})$

所以

$f^\prime(x)=f(x)Ln(\frac{N}{ex})$

$=(\frac{N}{x})^xLn(\frac{N}{ex})$

可以知道，当$x>0$时，$(\frac{N}{x})^x$恒大于0

而$Ln(\frac{N}{ex})$为减函数

所以$f^\prime(x)$单调递减，$f(x)$在$(0,+\infty)$有极大值

而$Ln(1)=0$

所以当$\frac{N}{ex}=1$即$x=\frac{N}{e}$时$f^\prime(x)=0$，取得极大值。

然而需要注意，$x$为整数。所以，$x$应该为$\lfloor\frac{N}{e}\rfloor$或者$\lfloor\frac{N}{e}\rfloor+1$

分别计算这两个点对应的函数值取max即可。

不好算？可以对原函数取对数，再比较对数即可。

$Ln[f(x)]=xLn(\frac{N}{x})$

然后便得到了$D(N)=x$。然后需要处理是否无限小数。

这个更简单。容易知道$\frac{a}{b}[gcd(a,b)=1]$为有限小数当且仅当$b=2^{k_1}*5^{k_2}(k_1,k_2\in N)$

所以直接强行把$b$除掉所有的$2$因子和$5$因子就可以了。

注意提前除去$gcd(a,b)$。

代码：

    #include<bits/stdc++.h>
    #include<cctype>
    #define For(i,a,b) for(i=(a),i##end=(b);i<=i##end;++i)
    #define Forward(i,a,b) for(i=(a),i##end=(b);i>=i##end;--i)
    #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
    #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=(b);--i)
    using namespace std;
    template<typename T>inline void read(T &x){
        T s=0,f=1;char k=getchar();
        while(!isdigit(k)&&k^'-')k=getchar();
        if(!isdigit(k)){f=-1;k=getchar();}
        while(isdigit(k)){s=s*10+(k^48);k=getchar();}
        x=s*f;
    }
    void file(void){
        #ifndef ONLINE_JUDGE
        freopen("water.in","r",stdin);
        freopen("water.out","w",stdout);
        #endif
    }
    const int MAXN=110001;
    static int n;
    const long double e=2.71828182845904523536;
    inline void init()
    {
        read(n);
    }
    inline long double calc(int f,int x)
    {
        return x*log((long double)f/x);
    }
    inline void solve()
    {
        static int ans1;
        static int ans=0;
        Rep(i,5,n)
        {
            ans1=floor(i/e);
            if(calc(i,ans1)<calc(i,ans1+1))++ans1;
            ans1/=__gcd(ans1,i);
            while(ans1%2==0)ans1/=2;
            while(ans1%5==0)ans1/=5;
            if(ans1!=1)ans+=i;
            else ans-=i;
        }
        printf("%d\n",ans);
    }
    int main(void){
        file();
        init();
        solve();
        return 0;
    }