高精度問題

Time Limit:1000MS  Memory Limit:65536K
Total Submit:381 Accepted:107

Description

相信經過暑假一個月的培訓，大家應該已經掌握了高精度的算法了。但是往往比賽中涉及到高精度的問題并不多。而有些題目可能看起來需要高精度，而實際上并不需要。一個很好的例子就是3^p mod x, 初學者如果不知道同余的概念的話，可能會求出3^p先，然后再對x取余，然而這對p很大的時候是行不通的。。于是我們想到了邊乘邊取余，其基本的思想就是先把x的整數倍拿掉，因為他對最后的計算結果沒有影響，但是這種算法對于p超過1000000的時候就會顯得很慢了，你有沒有想到更好的辦法。
本題的任務就是給你一個p和x輸出3^p mod x

Input

每行一個數據 p和x，2 < p, x ≤ 1000000000, 輸入最后以0 0結束

Output

輸出3^p mod x

Sample Input

10 7
0 0

Sample Output

4

         這個題目老師教了我好幾遍我也沒懂。。。悲?。。?！

代碼如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int modExp(int a, int b, int n)
{  
    __int64 t, y;
    t=1;y=a;
    while(b!=0)
    {
          if(b%2==1)
          {
              t=t*y%n;
          }
          y=y*y%n;
          b=b/2;
    }
      return t;
}


int main()
{
    int b,n;
    while(scanf("%d %d",&b,&n)!=EOF&&(b!=0&&n!=0))
    {
        printf("%d\n",modExp(3,b,n));
    }
    return 0;
}