首页 > 代码库 > 高级'膜'运算

高级'膜'运算

人与人是不同的,有些人喜欢阅读满是图片的杂志,有些人喜欢在地下室引爆炸弹,而还有一些却喜欢一些麻烦的数字游戏。
每个人选择两个数字Ai和Bi写在纸上,其他人不能看见。过了一段时间后,每个人说出自己纸上的数字,然后每个人的目标是求出所有的Ai^Bi的和再模M的值,最先算出结果的,就是胜利者。
作为一个程序员,你当然有办法编一个程序,以最快的速度算出结果,赢得比赛。

 

Input Format:

第一行是一个数字M (1 <= M <= 45000)。第二行是数字H(1 <= H <= 45000)表示参加游戏的人数。接下来H行,每行两个数Ai和Bi(1<=Ai,Bi<=2^31),之间用一个空格隔开。

 

Output Format:

输出一个数字, (A1^B1+ A2^B2 + ... + AH^BH) mod M  的值。


Sample input:

16
4
2 3
3 4
4 5
5 6

Sample output:

题解:

快速幂,利用同余定理不断求余,余数相加再求余

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int m,h;
typedef unsigned long long LL;
LL A,B,sum=0;

LL my_pow(LL x,LL y)
{
    LL ans=1;
    while(y!=0)
    {
        if(y%2==1)
            ans=ans*x%m;
        y/=2;
        x=x*x%m;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>h;
    for(int i=1;i<=h;i++)
    {
        cin>>A>>B;
        sum+=my_pow(A,B);
    }
    cout<<sum%m<<endl;
    return 0;
}

 

高级'膜'运算