高精度问题

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;
}