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