描述： 人与人是不同的,有些人喜欢阅读满是女孩子的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏。比如ESSE论坛的一次活动： 每个人选择两个数字Ai和Bi写在纸上，其他人不能看见。过了一段时间后，每个人说出自己纸上的数字，然后每个人的目标是求出所有的AiBi的和模M的值，最先算出结果的，就是胜利者。 作为一个程序员，你当然有办法编一个程序，以最快的速度算出结果，赢得比赛。  输入： 输入包含Z组测试数据，输入第一行只包含数字Z。随后是测试数据：第一行是一个数字M(1≤M≤45000)。第二行是数字H（1≤H≤45000）表示参加游戏的人数。接下来H行，每行两个数Ai和Bi（1≤Ai，Bi≤231）。  输出： 对于每组测试数据，输出以下表达式的值： (A1B1+A2B2+...+AHBH)mod M.    样例输入： 3 16 4 2 3 3 4 4 5 5 6 36123 1 2374859 3029382 17 1 318132  样例输出： 2 13195 13
幂的计算方法 首先将指数变成二的幂次和的形式。如5=1+4=20+22，11=1+2+8=20+21+23。如果b可以表示为的形式，那么ab可以表示为  
表面上看这样的表达式更复杂了，但注意到上面的表达式的乘积项不超过(log2b)，同时，形如（i=0,1….）有如下的递推式: a^(2^(i+1))=(a^(2^i))^2 也就是说，后项可以通过前项的平方来得到。所以可以先将形如a^(2^i)（i=0,1….）的值求出来，记为r i=a^(2^i)（i=0,1….log2b）,则a^b=rb1*rb2*rb3*.....*rbk，不超过(log2b)次乘法。 采用以上的方法计算乘方的时间复杂度为O(log2b)。
取模运算可以与加、减、乘、乘方交换次序； (a+b)%m=a%m+b%m a*b%m=(a%m)*(b%m) ab%m=(a%m)b 所以表达式的任何中间结果都可以进行取模运算，使得中间结果不至于太大而溢出。 本题的关键在于计算形如ab%m的表达式的值，因为b的值较大，采用连乘的方法是不行的，采用本节介绍的只需要O(log2b)次乘法和模运算的方法。
#include void cal(long long *r,long long a,long long m)//计算a的2^j次方对m取模的结果，用数组r存下来 { r[0]=a%m; for(int i=1;i<32;i++) r[i]=r[i-1]*r[i-1]%m; } long long calc(long long m,long long a,long long b)//计算a%m的值 { long long b1[32],r[32];//b1是b的二进制结果，r[i]等于a的2^j次方对m取模的结果 cal(r,a,m); int i=0; while(b)//将b用二进制形式表示，结果保存在b1中 { b1[i++]=b%2; b/=2; } int k=1; for(int j=0;j