Description
Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions AiBi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers.
You should write a program that calculates the result and is able to find out who won the game.
Input
Output
(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
【题意】给出h组a,b的值,求a1^b1+a2^b2+...+an^bn之和mod p的值
【思路】快速幂二进制取模算法
参考资料:http://www.cnblogs.com/yan-boy/archive/2012/11/29/2795294.html
http://blog.csdn.net/zhangv123/article/details/47953221
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; int fun(long long int a,long long int b,long long int p)
{
long long int res=;
while(b)
{
if(b&) res=res*a%p;
a=a*a%p;
b>>=;
}
return res;
}
int main()
{
long long int t;
long long int a,b,h,p;
scanf("%lld",&t);
while(t--)
{
long long int ans=;
scanf("%lld%lld",&p,&h);
for(int i=;i<=h;i++)
{
scanf("%lld%lld",&a,&b);
ans=ans+fun(a,b,p); }
ans=ans%p;
printf("%I64d\n",ans);
}
return ;
}