0019：快速冪
題目鏈接：//www.luogu.com.cn/problem/P1226
給你三個整數 a,b,p，求 a^b mod p 的值。
這道題就是快速冪的模板題。
那麼，什麼是快速冪呢？
普通的冪運算就是讓 b 個 a 相乘，但這樣的時間複雜度較高，有 O（n）
接下來就要介紹一種時間複雜度只有O（log n）的演算法。
眾所周知，任何十進位數都可以拆成幾個2^n 相加。如 11=1011=2^3+2^1+2^0。
同理，冪運算可以表示為a^1+a^2+a^3……（不是每個數都有，取決於指數）
進行冪運算時，我們可以將指數轉化2進位，然後判斷它在i維是否為1，如果是，讓結果 *（a^i）。
上程式碼：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 long long a,b,p;//一定要用long long，不然只有36分 5 long long we=1;//一定要賦值為1，如果賦值為0的話所有結果全都是0 6 cin>>a>>b>>p; 7 cout<<a<<"^"<<b<<" mod "<<p<<"="; 8 while(b){ 9 if(b&1){//如果b的最後一位是1 10 we=(we*a)%p;//結果*a^i 11 } 12 a=(a*a)%p;//a平方 13 b>>=1;//捨棄b的最後一位 14 } 15 cout<<we; 16 }
