求A^B的最后三位数表示的整数（1<=A,B<=1000）



输入
n个测试实例，每个实例给出两个正整数A,B

输出
输出A^B的最后三位（没有前导0）

样例输入
2
2 3
12 6
样例输出
8
984
提示

来源

#include<stdio.h>
#include<math.h>
int main()
{

      int n,a,b,c,i,s;
      scanf("%d",&n);
      for(i=0;i<n;i++)
      {
          scanf("%d%d",&a,&b);
          c=pow(a,b);
          s=c%1000;
          printf("%d",s);
          printf("\n");
      }
      return 0;

}
/*这样写为什么会出现如下错误，希望能有大神帮我看看我看看我错在哪了=================/test0.out
Right:
624

-----------------
Your:
-648

=================

[ 本帖最后由 water95 于 2015-4-11 11:21 编辑 ]

用普通类型数据会造成溢出的，你肯定无法计算出10的1000次方的，这要找规律。

你能帮我改一下吗？这样改对吗？
#include<stdio.h>
#include<math.h>
int main()
{

      int n,a,b,i;
      double c,s;
      scanf("%d",&n);
      for(i=0;i<n;i++)
      {
          scanf("%d%d",&a,&b);
         c =pow(a,b);
          s=c%1000;
          printf("%.0f",s);
          printf("\n");
      }
      return 0;

}

http://
这里有个求幂的，不知道有没有用

谁能看看我这个该怎么改，谢谢了

#include<stdio.h>
int Montgomery(int n,int p)
{ //快速计算(n^P)%1000的值
      int k=1;
      n%=1000;
     while(p!=1)
     {
         if(0!=(p&1))k=(k*n)%1000;
         n=(n*n)%1000;
         p>>=1;
    }
    return(n*k)%1000;
}
int main()
{
   int A,B,C;
   int n;
   int i;
   scanf("%d",&n);
  while(i<n)
  {
   scanf("%d%d",&A,&B);
    C=Montgomery(A,B);
    printf("%d",C);
  }
    return  0;
}

[ 本帖最后由 windfiresnow 于 2015-4-11 10:58 编辑 ]

这题的思路我觉得是这样：x的n次方最后3位数取决于数据x的末尾两位数，同时该末尾两位数从1至n次方肯定有一个循环规律，所以求一个数的1000次方的结果后3位并不需要求1000次方，只要找到尾数变化的规律即可

规模有点小，怎么做都可以AC。如果把范围扩大到1亿你们会怎么做？

送一小段代码给大家参考

#include <stdio.h>

int cal(int a, int b)
{
    int r;
    if(b == 0) return 1;
    r = cal(a, b >> 1);
    r = r * r % 1000;
    if(b & 1) r = r * a % 1000;
    return r;
}

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

经常会在算法帖里面看到b版的身影和简洁到令人发指的代码，哈哈

就让我来解释一下吧
b版代码中解决这个问题的核心思想是把次方拆成一个个乘法，每次乘法截留指定尾数。
不过b版的次方运算比较巧妙，a^b（a的b次方）按b的奇偶分情况运算
b 为偶数，化为 (a^2)^(b/2)
b 为奇数，化为 (a^(b-1))*a

是正确的？不过我看不懂。。。if（b & 1）是什么意思？