快速冪

相關例題：

求 a 的 b 次方對 p 取模的值。

0≤a,b,p≤1e9
資料保證 p≠0

常規解決方法（暴力解法）

C語言的學習讓我們深深的愛上了for迴圈的使用，在我看到這題的時候，不加思索，迴圈用b控制迴圈的次數，得出結果之後再取模。解決！但是當我們想當然的把自己的程式碼提交之後，就會發現「時間超限！」那麼有沒有什麼可以解決時間超限的問題，也就是可以讓迴圈的次數儘可能少。這就引出了今天要介紹的內容：快速冪

快速冪的理解

以3^{6為例子，我們發現3}6=3^3*33，3^{3又可以化為3}1*3^1，當然最後的結果要在乘以3，不難發現，如果我們可以不斷地把指數進行拆分，這樣就簡化了運算的步驟，從而實現了縮短時間的目的。

指數為奇數和指數為偶數的不同情況

當指數為偶數的時候較為簡單，每一次都將指數拆分（也就是把指數/2），當指數為奇數，或者拆分後指數為奇數時，再將結果乘以底數即可。

如圖所示，以3^100的拆分為例子。

快速冪的解法（遞迴版）

經過上面的圖片我們不難發現，經過拆分，最後都可以變為底數^1，因此，我們可以設計一個遞迴函數，當指數為1的時候，返回值為本身，如果大於1，就返回拆分後的結果。這樣一來就實現了快速冪演演算法的實現。

取模運算

當然我們掌握了快速冪的求解之後，還要掌握的就是取模運算
a ^ b % p = ((a % p)^b) % p

程式碼部分

有了以上的知識基礎知識，我們就可以進行程式碼部分的編寫在這離我們運用Java語法進行編寫

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
long a,b,p;
a=in.nextLong();
b=in.nextLong();
p=in.nextLong();
long ans=f(a,b,p);
ans=ans%p;
System.out.println(ans);
}
private static long f(long m,long n,long t) {//
if(n==0)
return 1;
long c=f(m,n/2,t)%t;
if(f1(n)==1)
return cc%tm%t;
return c*c%t;
}
private static long f1(long n) {
if(n%2=0)
return 0;
else
return 1;
}
}