【POJ – 1995】Raising Modulo Numbers（快速幂）

–>Raising Modulo Numbers

Descriptions:

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

Z

M

H

A1  B1

A2  B2

A3  B3

………

AH  BH

有Z组数据   求(A1B1+A2B2+ … +AHBH)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;
    }
}

 

posted on 2019-07-18 22:22 Sky丨Star 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为sky-stars原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/sky-stars/p/11210434.html