#include
     
      #define LL long longusing namespace std;//快速幂算法LL pow(LL a,LL b,int m){    LL r=1,base=a;    while(b!=0){        if(b&1)        r=r*base%m;//同余模公式         base=base*base%m;//同余模公式         b>>=1;    }    return r;}int main(){    int n,r,m;    cin>>n;    while(n--){        cin>>r>>m;        LL x,y,sum=0;        for(int i=0;i
      
       >x>>y;            sum+=pow(x,y,r);        }        cout<
       
        <
       
      
     

快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为O（log2N），与朴素的O（N）相比效率有了极大的提高。

以下以求a的b次方来介绍

^[1]  

把b转换成 。

该二进制数第i位的权为

例如

11的二进制是1011

11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1

因此，我们将a¹¹转化为算

 

了解到了这个便有了思路，

在计算幂的过程中，为了保证不溢出，使用同余模公式：

(a+b)%m=(a%m+b%m)%m;

(axb)%m=(a%mxb%m)%m;