double的范围足够大,所以一些对精度要求不高的题目可以近似计算

k^n=p

已知n,p求k
很简单 k=pow(k,1/n)
都用double存就可以了。

N^N

  • 求其最右边几位

$$n^n=10^{lg(n^n)}=10^{nlg(n)}=10^{[nlg(n)]}10^{nlg(n)-[nlg(n)]}$$
因此其最右边几位的近似值即$10^{nlg(n)-[nlg(n)]}$

  • 个位
    矩阵快速幂取模

fibroncci

$$ f(n)=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$$
n足够大(其实不需要多大)时,减去的可以忽略不计,然后可以运用上面的规则近似计算。

cantalan

$$C_n=\frac{(2n)!}{(n+1)!n!}$$
$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$