首页 > ACM题库 > HDU-杭电 > hdu 2035 人见人爱A^B-分治-[解题报告]C++
2013
12-26

hdu 2035 人见人爱A^B-分治-[解题报告]C++

人见人爱A^B

问题描述 :

求A^B的最后三位数表示的整数。
说明:A^B的含义是“A的B次方”

输入:

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

输出:

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

样例输入:

2 3
12 6
6789 10000
0 0

样例输出:

8
984
1

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=2035

法一:每次取余数

#include<stdio.h>
 #include<stdlib.h>
 int main()
 {
     int n,m,mul;
     while(~scanf("%d%d",&n,&m)&&(n||m))
     {
         mul=1;
         while(m--)
             mul=(mul*n)%1000;
             printf("%d\n",mul);
     }
     system("pause");
     return 0;
 }

法二:其实直接每次取余数就能过的 第一遍就是用这种方法过的 这次算是用二分加速过的吧 就是每次都讲底数平方 指数除以2 要是偶数没问题 要是奇数就在将多余的那部成到sum中(初始值为1)  不停地做循环知道b<=1 最后输出sum*a; 注意b开始不能取余数 否则会因为乘法的次数改变而出错

View Code 
  #include<iostream>
  using namespace std;
  int ex_pow(int a,long long b)
  {
      long long sum;
      a=a%1000;//a可以取余数 但b千万不要取余数 否则b较大时出错!!!因此WA了两次 
      sum=1;
      while(b>1)
      {         
               if(b%2==1)
               {         sum=(sum*a)%1000;
                         
               }
               else
               {
                       
               }
                a=a*a%1000;
                b=b/2;            
      }
      return  sum%1000*a%1000;
  }
  int main()
  {   
      long long a,b;
      while(cin>>a>>b)
      {               
                      if(a==0&&b==0)
                      break;
                      a=a%1000;
                      cout<<ex_pow(a,b)<<endl;
      }
     // system("pause");
      return 0;
  }

解题转自:http://www.cnblogs.com/mycapple/archive/2012/08/06/2624534.html