快速冪取模算法的引入是從大數(shù)的小數(shù)取模的樸素算法的局限性所提出的，在樸素的方法中我們計算一個數(shù)比如5^1003%31是非常消耗我們的計算資源的，在整個計算過程中最麻煩的就是我們的5^1003這個過程
缺點1：在我們在之后計算指數(shù)的過程中，計算的數(shù)字不都拿得增大，非常的占用我們的計算資源（主要是時間，還有空間）
缺點2：我們計算的中間過程數(shù)字大的恐怖，我們現(xiàn)有的計算機是沒有辦法記錄這么長的數(shù)據(jù)的，所以說我們必須要想一個更加高效的方法來解決這個問題
當(dāng)我們計算AB%C的時候，最便捷的方法就是調(diào)用Math函數(shù)中的pow方法，但是有時A的B次方數(shù)字過大，即使是雙精度的double也會溢出，這個時候為了得到AB%C的結(jié)果，我們會選擇使用快速冪取模算法，簡單快速的得到我們想要的結(jié)果。
為了防止數(shù)字溢出并且降低復(fù)雜度，我們需要用到下面的公式:
ab mod c = (a mod c)b mod c
這個公式的意思就是：積的取余等于取余的積的取余。很容易看出來這個公式是具有傳遞性的，這樣我們可以通過不斷的取余讓a越來越小，防止出現(xiàn)溢出的情況。
理論上，有了這個公式我們就可以寫代碼了，通過不斷的對a進(jìn)行取模保證結(jié)果不會溢出，這確實能計算出較大次方的冪的模，但是這種方法的復(fù)雜度仍舊是O(N)，并不快速。
為了更快速的計算出冪的模，我們還要依賴下面這個公式：
ab mod c = (a2)b/2 mod c , b為偶數(shù)
ab mod c = ((a2)b/2·a) mod c , b為奇數(shù)
這個公式很簡單，原理就是不斷的用a的平方來代替b，將b替換為原來的一半。因為我們通過第一個公式知道了一個數(shù)的模的相同次方的模相同（這句話說的有點繞，就是公式一的意思）。那么我們用a*a%c的結(jié)果來代替a效果是一樣的。
所以根據(jù)上述的公式，我們得到復(fù)雜度O（logN）這樣的計算快速冪的方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(); int res = 1; a %= c; for (; b != 0; b /= 2) { if (b % 2 == 1) res = (res * a) % c; a = (a * a) % c; } System.out.println(res); }} |
這個算法大概如此，第一步先a%=c是為了將a縮小一些，防止在for中第一次進(jìn)行a*a的時候數(shù)字溢出。在for循環(huán)中，如果是b為奇數(shù)則令res=res*a，直接先將a乘到結(jié)果中去，最后做處理，又是為了防止數(shù)字溢出直接將res*a的結(jié)果mod c操作。這個for循環(huán)中，早晚有一天b會等于1，進(jìn)入if分支，最后將res的值計算完畢mod c退出for循環(huán)，的到最后的結(jié)果。
總結(jié)
以上就是本文關(guān)于Java語言實現(xiàn)快速冪取模算法詳解的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/quinnnorris/article/details/77587096
