【Q374】Big Mod

題目： http://acm.uva.es/p/v3/374.html

說明：
　　簡單的題目，重點在於讓執行時間能夠最少，這才是這題的困難所在！數學基礎好一點的應該可以很快想到最佳解^^
　　這題也讓我一改之前的想法：迴圈執行效能、記憶體使用一定比遞回來的好。這題用遞迴寫法可以讓程式呈現BigO(1)，第一次用迴圈寫的時候卻需要BigO(n)，在效率來說確實落差很大；就記憶體來看，迴圈寫需要其他變數儲存過程的數值，而遞迴寫法只需要原本必須的三個變數：B、P、M，顯然也較迴圈來得優！

程式下載： http://yaushung.googlepages.com/2007021903.c

程式內容：

#include <stdio.h>

int bigMod(int B, int P, int M) ;

int square(int n) ;

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


int bigMod(int B, int P, int M) {
    if(P==0)
        return 1 ;
    else if((P%2)==0)
        return square(bigMod(B, P/2, M)) % M ;
    else

        return (B * bigMod(B, P-1, M)) % M ;
}

int square(int n) {
    return n*n ;
}