第三次周赛G题(POJ-1995)

68 阅读 0 评论 45 点赞

我是靠谱客的博主年轻蛋挞，这篇文章主要介绍第三次周赛G题(POJ-1995)，现在分享给大家，希望可以做个参考。

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

问题简述：求(A1B1+A2B2+ … +AHBH)mod M的值。

Point：用快速幂计算。

Get：这里用的是分配律：(a+b) mod c=(a mod c+ b mod c) mod c。
相关链接：https://www.cnblogs.com/yexiaozi/p/5698426.html

AC代码：

#include <iostream>
using namespace std;
long long k(long long a, long long b, long long c)
{
long long cnt=1;
while (b)
{
if (b % 2)
{
cnt = cnt * a%c;
}
b = b / 2;
a = a * a%c;
}
return cnt;
}
int main()
{
int i,z,M,H[45000][2];
cin >> z;
while (z--)
{
long long sum = 0;
cin >> M>>i;
for(int j=0;j<i;j++)
{
cin >> H[j][0] >> H[j][1];
sum += k(H[j][0], H[j][1], M);
}
cout <<sum%M<< endl;
}
}