Vjduge J 同于定理-------快速幂模m算法 解决 a^b %m 问题

• 题目概述
• 解决方案
• 思考
• 代码
• 总结

题目概述

求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方” Input
输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。 Output
对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。 Sample Input
2 3
12 6
6789 10000
0 0 Sample Output
8
984
1

解决方案

思考

第一眼看到这个问题，卧槽， 先要求n 次方， 还要取模？这尼玛怎么写？？？ 运算这么多次肯定要涉及大整数了。 不能方。 但是有感觉很蠢，这要多费功夫啊(╥╯^╰╥)。 不行， 我很懒，想想办法。 查询相关的资料（google一下）， 嗯， 要用到数论的知识， 这就触及到我的知识盲区了。。恶补一番， 快速幂模算法，同余的概念 及 公式。。。。（此处省略一百字）， 嗯，然后就会做了。。。

代码

#include typedef long long LL ; LL pow(LL a, LL b, LL m){ LL ans = 1 ; while(b){ if(b&1) ans = ans * a % m ; //判断当前最后一位是否为1,模m防止过大溢出， 可参考模的运算性质 a = a * a % m; //同上 b >>= 1; //位的右移运算 } return ans; } int main(){ LL a, b; scanf("%lld%lld", &a, &b); while(a && b){ printf("%lld ", pow(a, b, 1000)); scanf("%lld%lld", &a, &b); } return 0; }

总结

该题如果直接用什么大整数做的话可以说是相当愚蠢了，但是只要学习了数论的一些知识，就很简单了。唉，数论算法，这该死的香甜。。。。 萌新一枚，文章有什么问题批评指正，有争议的地方也可以和我探讨哦！
（欢迎关注我，一个成长中的小白 /手动狗头）。