博客停了差不多三個月， 雖然這一段時間在學算法， 但從來沒有寫博客。 今天看了一上午的快速冪，突然想寫寫博客， 增加一下自己的記憶！這個博文知識簡單介紹一下算法中取余的原因
1 至於快速冪的概念不詳細記錄了。當我們想求a的b次冪對c取余時，我們會直接想到用這個算法：
int ans = 1;
for( i = 1; i <= b; i++)
{
ans = ans * a;
}
ans %= c;
這個算法的時間復雜度體現在for循環中，為O（b）.這個算法存在著明顯的問題，如果a和b過大，很容易就會溢出。因此需要用到離散數學知識（該知識點我也沒學過，度娘教的^_^）
定理1：
2 由上面的公式可以推出：
把a看成 a * 1, 故由定理1可得出上面的公式。由此得到改進版本：
int ans = 1;
a = a % c; //加上這一句
for(int i = 1;i<=b;i++)
{
ans = (ans * a) % c；//這裡再取了一次余
}
ans = ans % c；
這個算法在時間復雜度上沒有改進，仍為O(b)，不過已經好很多的，但是在c過大的條件下，還是很有可能超時，所以，我們推出以下的快速冪算法。
3 快速冪算法依賴於以下明顯的公式，我就不證明了，很簡單理解。
4 由此得到改進版本：
int ans = 1;
a = a % c;
if(b%2==1)
ans = (ans * a) mod c; //如果是奇數，要多求一步，可以提前算到ans中
k = (a*a) % c; //我們取a2而不是a
for(int i = 1;i<=b/2;i++)
{
ans = (ans * k) % c;
}
ans = ans % c;
5 我們可以看到，我們把時間復雜度變成了O(b/2).當然，這樣子治標不治本。但我們可以看到，當我們令k = (a * a) mod c時，
狀態已經發生了變化，我們所要求的最終結果即為(k)^b/2 mod c而不是原來的a^b mod c，所以我們發現這個過程是可以迭代下去的。
((迭代就是把這一次算的值作為下一次循環的初始值，所以可以更簡化該算法））
當然，對於奇數的情形會多出一項a mod c，所以為了完成迭代，當b是奇數時，我們通過 ans = (ans * a) % c;來彌補多出來的這一項，
此時剩余的部分就可以進行迭代了。 形如上式的迭代下去後，當b=0時，所有的因子都已經相乘，算法結束。於是便可以在O（log b）的時間內完成了。
於是，有了最終的算法：快速冪算法。
((說實話， 我對這個簡化有點糊塗，關於在O（log b）的時間內就可以完成， 就假裝懂了吧， 以後慢慢理解吧))
6
int ans = 1;
a = a % c;
while(b>0)
{
if(b % 2 == 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c;
}
7 將上述的代碼結構化，也就是寫成函數：
int PowerMod(int a, int b, int c)
{
int ans = 1;
a = a % c;
while(b>0)
{
if(b % 2 = = 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c;
}
return ans;
}
這就是最後的優化代碼了。以上內容是抄襲的， 只不過自己又寫了一遍。如果看不懂我寫的的可以點下面網址：
http://wenku.baidu.com/link?url=PdtuRuYTZSIfAC3TZCiHSx3fk7cEn3yuZBiYwbx-b7h_TOxNyOQtNOaUepEmxw56jhnPePqAdebOH6QL- pvmhFCYYdzGhYRneUM_oZTpxwO
有關於快速冪的算法的推導，還可以從另一個角度來想。我就不介紹了。
