poj 1995(快速幂)

poj 1995

根据题目公式
$$(A_1^{B_1}+A_2^{B_2}+ … +A_h^{B_h})\mod M$$
快速幂即可

#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<cmath>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
#define ll long long
int h;
ll m;
ll ans;
ll poww(ll a, ll b)
{
    ll ans = 1, base = a%m;
    while (b!=0)
    {
        if (b&1!=0)
        {
            ans = (ans*base)%m;
        }
        base = (base*base)%m;
        b>>=1;
    }
    return ans;
}
int main()  
{  
    int kase;
    scanf("%d", &kase);
    while (kase--)
    {
        scanf("%lld%d", &m, &h);
        ans = 0;
        for (int i=1;i<=h;i++)
        {
            ll a,b;
            scanf("%lld%lld", &a, &b);
            ans = (ans+poww(a,b))%m;
        }
        printf("%d\n", ans%m);
    }
    return 0;  
}