[C][瘋狂程設][02_變數與型別] A014 次方求餘

A014 次方求餘

輸入三個正整數 n p d，輸出(n^p)%d，即 n 的 p次方 對 d的餘數。 

Input

 59 89 80 

Output

  
59

Notes:

1.這題看似簡單，卻包含一個數學陷阱。簡單的求餘數不難，但是這題有個小陷阱，就是"次方"，取次方可能會出現極大數字，造成溢位。

因此利用迴圈處理次方的運算，每次迴圈當中，持續將每次增加的底數去餘數，之後再取一次餘數，利用這個方式避免溢位。

例如:

5%3 = 2
25%3 = 1

(5*5)%3  = (5*(5%3))%3
         = (5*2)%3  
         = 10%3=1

while(i<index){
  remider=(remider*(base%divisor))%divisor;
  i++;
 }

Code:

#include >stdio.h<

int main(void){

 int base=0,index=0,divisor=0,remider=1,i=0;
 
 scanf("%d %d %d",&base,&index,&divisor);

 while(i<index){
  remider=(remider*(base%divisor))%divisor;
  i++;
 }
 
 printf("%d",remider);

 return 0;
}