【POJ

-->Raising Modulo Numbers

Descriptions:

题目一大堆，真没什么用，大致题意

Z

M

H

A₁  B₁

A₂  B₂

A₃  B₃

.........

A_H  B_H

有Z组数据   求(A₁^B₁+A₂^B₂+ ... +A_H^B_H)mod M.

Sample Input

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

Sample Output

2
13195
13

题目链接
https://vjudge.net/problem/POJ-1995

 

直接快速幂即可

 

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 30
using namespace std;
ll mod;
ll ans;
int Z,M,H;
ll qpow(ll a, ll n)//计算a^n % mod
{
    ll re = 1;
    while(n)
    {
        if(n & 1)//判断n的最后一位是否为1
            re = (re * a) % mod;
        n >>= 1;//舍去n的最后一位
        a = (a * a) % mod;//将a平方
    }
    return re % mod;
}

int main()
{
    cin>>Z;
    while(Z--)
    {
        ans=0;
        cin>>M>>H;
        mod=M;
        for(int i=0;i<H;i++)
        {

            ll a,b;
            cin>>a>>b;
            ans+=qpow(a,b);
        }
        ans=qpow(ans,1);
        cout<<ans<<endl;
    }
}