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

高级'膜'运算

2024-09-07 16:25:39   219人阅读

人与人是不同的,有些人喜欢阅读满是图片的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏。
每个人选择两个数字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;
}

 

高级'膜'运算


联系
我们