前言
快速冪算法一般用于高次冪取模的題目中，比如求3的10000次方對7取模。這時候有些同學會說：這還不簡單？我直接調用pow函數然后對結果%7不得了么？可是3的10000次方這么龐大的數字，真的能儲存在計算機里么？顯然是不行的，只會得到一個錯誤的數字，那么我們怎樣才能得到答案呢？首先我們要知道取模的運算法則。
( a * b ) % c = ( ( a % c ) * ( b % c ) ) % c (要是不知道為什么請自行百度）
在了解了取模的運算法則后就讓我們進入今天的正題吧！

快速冪
既然我們知道了取模的運算法則，那么3的一萬次方%7轉化成（（（3%7）*3）%7）*3）%7…
這樣便不會出現數字太大超出范圍的情況。這一種我們可以采用循環的方法實現。

#include<stdio.h>
int main()
{int a = 3, b = 10000;int ans = 1;while (b--){ans = ans * a % 7;}printf("%d\n", ans);return 0;
}

可是這樣要進行一萬次的循環，效率非常之低，這時就需要用到我們的快速冪算法。
首先3的一萬次方=9的5千次方=81的2500次方…以此類推。如果我們對底數平方處理，那么我們只需要將冪除以2即可。這樣能極大地提高效率，但是要注意特殊情況，比如3的10001次方此時10001并不是一個偶數，但是我們可以把它變成偶數，可以變為3*3的一萬次方，也就是說我們在進行快速冪算法時要考慮冪的奇偶情況。
下面我用代碼來為大家展示。

#include<stdio.h>
int main()
{int a = 3, b = 10000;int ans = 1;while (b)//當b大于0時進行循環{if (b%2==1)ans = ans*a%7;b /= 2;a = a*a%7;}printf("%d", ans);return 0;
}

那么有沒有更快的方式呢？當然有，我們知道使用位操作符和移位操作符的運算速度比使用/和%要快上好多。那么我們就可以對代碼進行這樣的修改。

#include<stdio.h>
int main()
{int a = 3, b = 10000;int ans = 1;while (b){if (1 & b)//若果1&b=1說明b是奇數，如果1&b=0說明b是偶數ans = ans*a%7;b >>= 1;//相當于b=b/2a = a*a%7;}printf("%d", ans);return 0;
}

這就是快速冪算法，如果覺得博主講得不錯請給博主一個贊支持一下吧~（如果能再收藏一下就更好了），那么今天的分享就到這里，我們下期再見！