d636

輸入說明 ：

每個測資點僅一組測資，不必EOF讀檔。 測資包含一列兩個數字a和b (1<=a<=65535 , 1<=b<=2147483647)

輸出說明 ：

請輸出a^b的值，為了避免數字太大，將結果mod10007輸出就可以了！

這是討論區的答案

要解這題要先知道

a^b%10007=(a%10007*a%10007..... 乘以b次)%10007

知道這件事之後,這個程式碼就是這樣

ex 10009^12 %10007 12分解成2進位是1100

可以看成(10009^8%10000710009^4%10007) %10009 而10009^2%10007可以看成 (10009%10007)35%10009

 10009^3%10007可以看成(10009%10007)10009%10007)10009%10007

#include <stdio.h>
int powmod(int a, int b) 
{
  int bin=1;
  int i;
  int res=1;
  int tmp=a%10007;

  for(i=0; i<32; i++) 
  {
    if(b & bin)
      res = res * tmp % 10007;
    bin <<= 1;
    tmp = tmp * tmp % 10007;
  }
  return res;
}

int main() 
{
  int a, b;
  scanf("%d %d", &a, &b);
  printf("%d\n", powmod(a, b));
  return 0;
}