前言
暑假在看c++面經時，看到了騰訊的一道面試題，
題目大意是：求(2^1e10)%10000的值，限制了時間復雜度，
在C++中沒有Java和Python中的大數，不知道讀者朋友們可否AC此題，
正文
這道題可以用快速冪來AC，
請聽我詳細道來，
在學習了二進制相關知識后，我們知道任何一個數都可以用唯一的二進制表示，也就是說每一個數可以唯一表示為若干指數不重復的2的次冪的和，
舉個例子：假設b在二進制表示下有k位，則b可以表示為：
b=ck-12k-1+ck-22k-2+ck-32k-3+......+c121+c020
快速冪常見的模式為：
- 給定a,b,p的值，求(a^b)%p的值，a,b,p都是大數，1<= a ,b ,p<=1e10.
- 給定a,b,p的值，求(a*b)%p的值，a,b,p都是大數，1<= a ,b ,p<=1e10.
1. (a^b)%p
有上面的例子可知：
b=ck-12k-1+ck-22k-2+ck-32k-3+......+c121+c020
則 a^b= ac~k-1~2k-1+ac~k-2~2k-2+ac~k-3~2k-3+......+ac~1~21+ac~0~20
由于數學格式支持的不是很好，貼一個圖說明一下，
演算法分析：
根據上式我們發現，原問題被我們轉化成了形式相同的子問題的乘積，并且我們可以在常數時間內從2k-1項推出 2k項，
這個演算法的復雜度是O(logN) 的，我們計算了logN個 2K次冪的數，然后花費 logN 的時間選擇二進制為 1 對應的冪來相乘，
來個題目練練手 ：計算 (a^b)%p的值
#include<iostream>
using namespace std;
typedef long long LL;
LL a,b,p;
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
LL ans=1%p; // 初始ans
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p; //反復平方
b>>=1;
}
printf("%lld\n",ans);
return 0;
}
2.(a*b)%p
同第一張模板類似，同理：
來道題練練手：求(a*b)%p
#include<iostream>
using namespace std;
typedef long long LL;
LL a,b,p;
LL ans;
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
while(b)
{
if(b&1) ans=(ans+a)%p; // 累加每個2^k
a=a*2%p;
b>>=1;
}
printf("%lld\n",ans);
return 0;
}
注意事項
由于快速冪的資料很大，在使用c++做題時，用單純的cin來輸入測驗用例很慢，會導致超時，
在這里給兩個小建議：
- cin前面加上這條取消同步的陳述句
cin.tie(nullptr)->sync_with_stdio(false);
- 用scanf()來讀取，
最后
關于快速冪的題型還有很多，比如快速冪矩陣，計算斐波那契數等，
這篇文章所講的只是快速冪的初階內容，我在后面會為大家分享更高階的快速冪知識，
好啦，就先到這里了，我們下期再見！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/302121.html
標籤：其他