poj1995 Raising Modulo Numbers 整数型快速幂 算法的应用

#include<iostream>  
#include<cstdio>  
#include<list>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<stack>  
#include<map>  
#include<vector>  
#include<cmath>  
#include<memory.h>  
#include<set>  
  
#define ll long long  
#define LL __int64  
#define eps 1e-8  
  
//const ll INF=9999999999999;  
  
  
#define inf 0xfffffff  
  
using namespace std;  
  
//vector<pair<int,int> > G;  
//typedef pair<int,int> P;  
//vector<pair<int,int>> ::iterator iter;  
//  
//map<ll,int>mp;  
//map<ll,int>::iterator p;  
//  
//vector<int>G[30012];  
  
ll quickmod(ll a,ll b,ll MOD)  
{  
    ll ans=1;  
    while(b)  
    {  
        if(b&1)  
        {  
            ans=(ans*a)%MOD;  
            b--;  
        }  
        b/=2;  
        a=a*a%MOD;  
    }  
    return ans;  
}  
  
int main(void)  
{  
    int t;  
    ll MOD;  
    int n;  
    cin>>t;  
    while(t--)  
    {  
        cin>>MOD>>n;  
        ll a,b;  
        ll ans=0;  
        for(int i=0;i<n;i++)  
        {  
            cin>>a>>b;  
            ans=(ans%MOD+quickmod(a,b,MOD))%MOD;  
        }  
        cout<<ans<<endl;  
    }  
}