其實我本來想要在第0篇(?)講組合數的
不過組合數需要用到模逆元
模逆元需要用到快速冪
所以就先講快速冪啦~
***底下所有的log都是以2為底哦***
快速冪是什麼呢？
首先先來說程式設計怎麼做「a的n次方」
(後面我都會把「a的n次方」寫成「a^n」哦)
最直覺的想法就是
int ans=1;
for (int i=0; i<n; i++) ans*=a;
這個方法一定是正確的
但是一個好的程式除了要求正確性之外
還要求好的執行效率
上面那個程式片段的時間複雜度很明顯是O(n)
(不知道時間複雜度的可以去看資訊之芽上課的ppt
https://sprout.tw/algo2018/ppt_pdf/complexity.pdf (這是pdf檔))
於是 有人想到一個好方法
如果先求出a^1、a^2、a^4、a^8……
有了a^1 平方就可以得到a^2
有了a^2 平方就可以得到a^4
以此類推
若n是2的整數次方
要算a^n是多少
只要算a^(n/2) 再平方就好了
那麼 求出a^n的時間複雜度就是O(log(n))
那如果n不是2的整數次方 該怎麼辦？
只要用上面算的過程中
得到的那幾個數字去湊就好了！
例如 a^13=(a^8)*(a^4)*(a^1)
用上面的方法
a^8、a^4、a^1在O(log(n))的時間複雜度就可以得到
而乘起來的過程 最多也不會乘超過log(n)次
所以複雜度是O(log(n))
快速冪就這麼完成了！
Code：
http://codepad.org/JGPrPFou
*小更新* B8 有更短更精簡的code 可以去看看！
另外
還有另一種做法：
對於任意的n
如果要知道a^(2n)是多少
只要先知道a^n的值 再平方就可以了
如果要知道的是a^(2n+1)的值
那就先算a^n的值 再平方 再乘上a就是答案
這個做法的時間複雜度也是O(log(n))
雖然真的硬要比執行效率的話
理論上會略為慢於第一種做法
但是在比賽中
數量級正確的做法通常都不會TLE的
而且我覺得這種寫法的code稍微簡單一點(個人感覺啦)
所以我是推薦這種的
Code：
http://codepad.org/ljX3mEzV
以上是這次的快速冪教學！
說實話
因為我只看過一次第一種做法的code
所以code寫得不怎麼優@@
如果有更好的寫法拜託告訴我
然後有問題都提出來哦~
下一篇預告：模逆元
你可能有興趣的文章...
全部留言
其實矩陣快速冪 就是用快速冪的概念去做矩陣乘法 就這樣 XDDD (好啦這樣講根本等於沒講 等我把第二篇的模逆元弄完 就來解釋矩陣快速冪囉！)
匿名
第一種寫法其實可以超簡單(? http://codepad.org/g9kYz7sc
{{comments[7].isShow ? '收合' : '展開' }}1則留言
呃 模逆元？快速冪？？？ 費馬小定理？ 呃，那如果mod 的數不是質數呢。。。小定理炸裂w
{{comments[8].isShow ? '收合' : '展開' }}1則留言
那個會在模逆元的第二篇說哦 因為那是比較偏向程式設計的領域 第一篇只是讓大家了解模逆元的意義
而且矩陣快速冪。。。就只是定義完矩陣乘法就沒了= = 其實那些東西比較偏向數學（？
{{comments[9].isShow ? '收合' : '展開' }}1則留言
匿名
B12表示：為什麼一個高中生比我這個大學生猛qq 而且我還資工系 怎麼辦
{{comments[13].isShow ? '收合' : '展開' }}1則留言
呃呃 其實還好啦 我們也只是先聽過而已 大學四年學到的東西 遠大於高中用的到的 所以到了畢業的時候 前面先修的優勢就沒差多少了啦 (而且 我以後應該是不會唸資工了XD)
