题解 P1925

Great_Influence · 2017-12-10 19:51:17 · 题解

高中数学题。

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

对两边同时取对数，得

求导，得

所以

可以知道，当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即可。

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

然后便得到了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;
    }