POJ1995 Raising Modulo Numbers

POJ1995 Raising Modulo Numbers

本题是裸的快速幂
但是由于快速幂我一直忘，在此我加强一下记忆

问题：求a^b mod m
数学证明有点麻烦，我们可以举个例子：求2¹¹
我们可以把它写成二进制(1011)₂
要求2¹¹ ，即求2¹⁺²⁺⁸ =2⁰ * 2¹ * 2³
详细过程如下：

这样可能好理解一点
为了方便代码，我们可以把11，也就是b每次>>1，然后我们每次取到的永远是最后一位了，只需要取b&1就行了
我们再用一个base记录移位了几次，也就是当前是a的多少次方(注意，即使该位为0也需要更新base，因为我们每次都会进行移位
由于题目要mod m，取模运算是对加法，减法和乘法封闭的，所以如果搞不清楚的话，就在全部+或* 的地方取模就行了
总结：
(a+b)%n = (a%n + b%n) % n;
(ab)%n = ((a%n)(b%n)) % n;
(a-b)%n = (a+(-b))%n = ( (a%n) + ((-b)%n) ) % n
（注意不对除法封闭！！！）
代码：

#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<iostream>
using namespace std;
int z,h,x,y,m,ans;
int work(int a,int b){
	int base=a%m,ans=1;
	while (b!=0){
		if (b&1==1) ans*=base,ans%=m;
		base*=base,base%=m;
		b>>=1;
	}
	return ans;
}
int main()
{
	scanf("%d",&z);
	while (z--){
		ans=0;
		scanf("%d",&m);
		scanf("%d",&h);
		for (int i=1;i<=h;i++){
			scanf("%d%d",&x,&y);
			ans+=work(x,y)%m,ans=ans%m;
		}
		printf("%d\n",ans);
	}
	return 0;
}