OJ : 1090 :整数幂（多实例测试）

本文主要是介绍OJ : 1090 :整数幂（多实例测试），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

输入

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

输出

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

样例输入 

2
2 3
12 6

样例输出 

8
984

 思路：

        这个题的难点在于数字太大，如何进行计算。用常用的思想就是用pow函数进行求A的B次幂，之后%1000，进行打印就好了。但是这种算法会造成数据溢出，就比如最大的1000的1000次幂就很大，存不下，这时候我们就需要换一种算法，尽量让空间复杂度降低，时间复杂度降低。那我们就可以用下面的方法进行简化计算，具体的可以看注释。

代码：

#include<stdio.h>int main()
{int n;scanf("%d", &n);//输入有几组测试样例for (int i = 0; i < n; i++)//有几组样例就循环几次{int A, B;int num = 1;scanf("%d %d", &A, &B);for (int j = 1; j <= B; j++)//循环依次求A的B次幂，但是是依次进行累乘求的{num = num * A % 1000;//为什么这个就能求到最后三位数？//因为当num大于1000时，就取后三位进行下一次累乘，这样不会影响前面的数，// 比如 666*666%1000=556，556*666%1000=296// 666*666=443556 ， 443556*666=295408296，295408296%1000=296//当num小于1000时，取余就不会影响数的大小}printf("%d\n", num);}return 0;
}

这篇关于OJ : 1090 :整数幂（多实例测试）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---