UVa OJ - 374 Big Mod

The following program is my ACcepted code for UVA-374 .
It's a for everybody to learn and discuss.
If there is any mistake or comment, please let me know.  :D

此乃UVA 374 的AC code!

歡迎一同討論學習，如有錯誤與任何建議請留言 : )

點這裡看題目 Click here to see this Problem!

在乘法時可以先把數字分開 mod，在乘起來 mod，這樣結果會一樣
Ex: B^P mod M = ( (B^(P-1) mod M) * (B mod M) ) mod M

所以我用Divide and Conquer來解決他
先把 B^P 分成 B^(P/2) * B^(P/2)。
(如果P為奇數就再乘一個 P)
用遞迴的方式求出答案
大概是這樣的感覺  B^P mod M = (B^(P/2) mod M) * (B^(P/2) mod M) mod M

//This program is for UVA 374 Big Mod
//題目來源 Problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=310

#include<stdio.h>
#include<iostream>
using namespace std;

long long int bigMod(int b, int p, int m)
{
    if(p == 0)// b^0 = 1
        return 1 % m;
     
    if(p == 1)
        return b % m;

    long long int tmp = bigMod(b, p/2, m);
 
    if( (p % 2) == 0)//p is even
        return (tmp * tmp) % m;
    else//p is odd
        return (tmp * tmp * b) % m;
}

int main()
{
    int B, M, P;
 
    while(scanf("%d %d %d", &B, &P, &M) != EOF)
    {
        printf("%lld\n", bigMod(B, P, M));
    }
    return 0;
}

Please feel free to use it after adding this blog as an reference. (http://autekroy.blogspot.tw) If there is any mistake or comment, please let me know. :D 

歡迎使用與分享任何內容，但請記得標示此部落格為出處。(http://autekroy.blogspot.tw/) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )

zh-CN → zh-TW

分開