RYIP在线题库
首 页   >   习题练习   >   提交
Problem1940--高级模运算

1940: 高级模运算

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

每个人选择两个数字Ai和Bi写在纸上,其他人不能看见。过了一段时间后,每个人说出自己纸上的数字,然后每个人的目标是求出所有的Ai^Bi的和再模M的值,最先算出结果的,就是胜利者。

作为一个程序员,你当然有办法编一个程序,以最快的速度算出结果,赢得比赛。


【 Input 】

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

【 Output 】

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

【 Sample Input 】

16
4
2 3
3 4
4 5
5 6

【 Sample Output 】

2

【 Source/Category 】