求$N^N$的首位数字

正如"大得多"定理所言,当$n\longrightarrow \infty$时:

$$  n^n \gg n! \gg a^n \gg n^b \gg ln^kn $$

$f(n) = n^n$的增长速度十分惊人.(其中$a>1,b>0,k\ge1$)

这个问题比求$n^n$的末位数字复杂不少,因为乘法中首位数字的确定与后面所有位上的数字都会有关系.

显然高精度运算是一个选择,不过当$n$巨大时还是可能会吃不消,这里介绍一种比较巧的办法.

这里先约定$lg(n)$即为$log_{10}(n)$;

1.任给一个数$n$,总有$n=10^{lg(n)}$.

2.$lg(n)$可以拆成$[lg(n)]+\{lg(n)\}$的形式,即拆成整数部分与小数部分之和.

3.一个数乘上$10^m$其首位数字不会发生变化($m$为非负整数),因此$10^{lg(n)}$的最高位即$10^{\{lg(n)\}}$的最高位,而$0\le\{lg(n)\}<1$,因此$ 1\le10^{\{lg(n)\}} \le  9$,因此可以用pow函数快速求出该幂,然后截断取整数部分即可.

贴一下代码:

 #include <bits/stdc++.h>
using namespace std;
int main()
{
double n;
scanf("%lf",&n); double m = n*log10(n);
m = m - floor(m); double res = pow(,m);
printf("%d\n",(int)res); return ;
}
上一篇:REdis之RDB配置问题


下一篇:7款让人惊叹的HTML5粒子动画特效(转载)