P2759奇怪的函数

· · 题解

看到没有牛顿迭代法，我来水一波
首先，牛顿迭代公式

x=x_0-\frac{f(x_0)}{f'(x_0)}

对于此题，由于n可能很大，直接对x^x求解不现实
考虑如何减小运算值

x^x=10^{n-1} x log_{10}x=n-1 x log_{10}x-n+1=0

然后对左边求导，得

(x log_{10}x-n+1)'=\frac{1}{ln10}+log_{10}x

于是可以写出此题的迭代公式

x=x_0-\frac{x_0 log_{10}x_0-n+1}{\frac{1}{ln10}+log_{10}x_0}

那么代码实现就贼简单辣！
注意一下浮点数要向上取整即可

#include<cstdio>
#include<cmath>
double solve(double n,double x0)//牛顿法
{
    double x=x0-(x0*log10(x0)-n)/(log10(x0)+1/log(10));
    while(abs(x-x0)>1e-10)//控制精度，实际上没必要那么高
        x0=x,x=x0-(x0*log10(x0)-n)/(log10(x0)+1/log(10));
    return x;
}
int main()
{
    int n,ans;
    scanf("%d",&n);
    --n;//这样方便之后的处理
    ans=solve(n,38);
    if(int(ans*log10(ans)+0.5)<n)++ans;//检测解是否为整数，不是则向上取整
    printf("%d",ans);
}

附：据说牛顿迭代是二阶收敛的，但涉及到极限的东西对我而言是玄学
所以复杂度大概也是O(玄学)吧（逃）