OI中的一些数学小技巧

本文主要是介绍OI中的一些数学小技巧，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在OI比赛中，如果能够灵活地运用一些数学小技巧，是能够很好地优化计算的时间和正确性的。
既然说了是小技巧，那么这些指的都是一些技巧，一般是不会单独成题的。

光速幂

有的时候，我们要去求解一个数或者一个矩阵的若干次幂，而这个指数在一般情况下是暴力无法接受的，这个时候我们会想到使用快速幂，即：
\(a^n=\begin{cases}\left(a^2\right)^{\dfrac{n}{2}}&2\mid n\\ a\left(a^2\right)^{\dfrac{n-1}{2}}&2\nmid n\end{cases}\)
这种做法可以做到优秀的 \(O(logn)\) 的复杂度。
但是，如果我们继续提高 \(n\) 的上限，long long存不下了呢？
栗子：Luogu P1397 [NOI2013] 矩阵游戏
这道题目有一个特别和善的数据范围： \(n \leqslant 10^{1000000}\)
似乎要写高精了，如果还是仿照快速幂的方式写，不难发现，由于高精度是按位处理，我们会发现，我们的复杂度会被卡到 \(O(log^2n)\) ，这个复杂度是我们无法接受的。
但我们想想，我们存的高精度是十进制的，如果我们用十进制来做快速幂，会怎么样？
我们考虑这样的形式：
\(a^n=\left(a^{10}\right)^{\left\lfloor\dfrac{n}{10}\right\rfloor}*a^{n \bmod 10}\)
我们只需要先预处理出 \(a^2\) 到 \(a^9\) 即可。
这样，我们规避了高精度除单精的问题，可以将时间优化到 \(O(logn)\) 了。
不难发现，我们平时写的快速幂就是光速幂的一种特殊形式，也就是对于二进制的处理方法
那么，是不是对于任意k进制，都可以用光速幂呢？
其实在形式上都是一样的，就是把上面的 \(10\) 换成 \(k\) 就可以了。
闲话（不知道正不正确，欢迎大佬指正）：那么对于不同的 \(n\) ，最优的 \(k\) 会是多少呢？
由于我们需要进行预处理，首先会有一个 \(k\) 的运算，如果不考虑做除法的时间，后面的运算是 \(log_kn\) 的复杂度
那么它的总复杂度是 \(k+log_kn\) ，这个函数是先减后增的。
我们来找它的极小点，对 \(k\) 求导
\((k+\operatorname{log}_kn)'=(k)'+(\operatorname{log}_kn)'=1+\left(\dfrac{1}{\operatorname{log}_nk}\right)'\)
\(\left(\dfrac{1}{\operatorname{log}_nk}\right)'=-\dfrac{1}{\operatorname{log}_n^2k}*(\operatorname{log}_nk)'=-\dfrac{1}{\operatorname{log}_n^2k}*\operatorname{log}_ne(\operatorname{ln}k)'=-\dfrac{\operatorname{log}_ne}{k\operatorname{log}_n^2k}\)
\((k+\operatorname{log}_kn)'=1-\dfrac{\operatorname{log}_ne}{k\operatorname{log}_n^2k}\)
当导数取 \(0\) 时：\(0=1-\dfrac{\operatorname{log}_ne}{k\operatorname{log}_n^2k}\)
则 \(\dfrac{\operatorname{log}_ne}{k\operatorname{log}_n^2k}=1\)
所以 \(\operatorname{log}_ne=\operatorname{log}_n^2k\)
所以 \(e=k^{\operatorname{log}_nk}\)
\(e^{\operatorname{ln}n}=k^{\operatorname{ln}nlog_nk}\)
\(n=k^{\operatorname{ln}k}\)
对于上面的题目，大概 \(k\) 是在 \(10^5\) 左右

这篇关于OI中的一些数学小技巧的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！