Java語言實現快速冪取模算法詳解

快速冪取模算法的引入是從大數的小數取模的樸素算法的局限性所提出的，在樸素的方法中我們計算一個數比如5^1003%31是非常消耗我們的計算資源的，在整個計算過程中最麻煩的就是我們的5^1003這個過程

缺點1：在我們在之后計算指數的過程中，計算的數字不都拿得增大，非常的占用我們的計算資源（主要是時間，還有空間）

缺點2：我們計算的中間過程數字大的恐怖，我們現有的計算機是沒有辦法記錄這么長的數據的，所以說我們必須要想一個更加高效的方法來解決這個問題

當我們計算A^B%C的時候，最便捷的方法就是調用Math函數中的pow方法，但是有時A的B次方數字過大，即使是雙精度的double也會溢出，這個時候為了得到A^B%C的結果，我們會選擇使用快速冪取模算法，簡單快速的得到我們想要的結果。

為了防止數字溢出并且降低復雜度，我們需要用到下面的公式:

a^b mod c = (a mod c)^b mod c

這個公式的意思就是：積的取余等于取余的積的取余。很容易看出來這個公式是具有傳遞性的，這樣我們可以通過不斷的取余讓a越來越小，防止出現溢出的情況。

理論上，有了這個公式我們就可以寫代碼了，通過不斷的對a進行取模保證結果不會溢出，這確實能計算出較大次方的冪的模，但是這種方法的復雜度仍舊是O(N)，并不快速。

為了更快速的計算出冪的模，我們還要依賴下面這個公式：

a^b mod c = (a²)^b/2 mod c , b為偶數
a^b mod c = ((a²)^b/2·a) mod c , b為奇數

這個公式很簡單，原理就是不斷的用a的平方來代替b，將b替換為原來的一半。因為我們通過第一個公式知道了一個數的模的相同次方的模相同（這句話說的有點繞，就是公式一的意思）。那么我們用a*a%c的結果來代替a效果是一樣的。

所以根據上述的公式，我們得到復雜度O（logN）這樣的計算快速冪的方法：

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中第一次進行a*a的時候數字溢出。在for循環(huán)中，如果是b為奇數則令res=res*a，直接先將a乘到結果中去，最后做處理，又是為了防止數字溢出直接將res*a的結果mod c操作。這個for循環(huán)中，早晚有一天b會等于1，進入if分支，最后將res的值計算完畢mod c退出for循環(huán)，的到最后的結果。

總結

以上就是本文關于Java語言實現快速冪取模算法詳解的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！