快速冪取模_C++，冪取模_C

快速冪取模_C++，冪取模_C

一、題目背景

　　已知底數a，指數b，取模值mo

　　求ans = a^b % mo

二、樸素算法（已知可跳過）

　　ans = 1，循環從 i 到 b ，每次將 ans = ans * a % mo

　　時間復雜度O(b)　　

 1 void power(int a,int b,int mo)
 2 {
 3     int i;
 4     ans=1;
 5     for (i=1;i<=b;i++)
 6     {
 7         ans*=a;
 8         ans%=mo;
 9     }
10 }

三、快速冪

　  先討論無需取模的

　　當b為偶數時：a^b=a^(b/2)*2=(a²)^b/2

　　當b為奇數時：a^b=a*a^b-1=a*(a²)^(b-1)/2

　　如   2⁸=（2²）⁴         2⁷=2*(2²)³

　　所以，我們可以如此迭代下去

　　2¹⁰=(2²)⁵=(2²)*[(2²)²]²

　　 ①       ②              ③

　　指數為10 是一個偶數，則底數2平方，指數變為一半 [ ①→② ]

　　指數為5 是一個奇數，則先將底數提出作為系數（2²），此時指數為4 是一個偶數，則底數2²再平方，指數再變為一半 [ ②→③ ]

　　歸納總結得到：

　　      當指數大於1時，若為 偶數 則將指數除以2，底數平方

                                   若為 奇數 則先提出一個為底數的系數（可直接把該系數乘進ans中），所以指數減1，然後再按照 偶數 的辦法做

　　不斷迭代下去，當指數為1時，則直接得出答案

　　最後只要將每次相乘時取模即可，時間復雜度O(log₂b)

 1 void power(int a,int b,int mo)
 2 {
 3     ans=1;
 4     a%=mo;
 5     while (b>0)
 6     {
 7         if (b%2==1) ans=ans*a%mo;
 8         b/=2;
 9         a=a*a%mo;
10     }
11 }