1、数论问题 Lecture by Hao Wu常见的数论问题 1.数的幂运算 2.欧拉定理的应用 3.素数测试 4.Pell方程 5.其它 案例 1：模的运算 Time Limit: 1000ms Special Time Limit:2500ms Memory Limit:32768KB 描述 人与人是不同的 ,有些人喜欢阅读满是女孩子的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏。比如 ESSE论坛的一次活动： 每个人选择两个数字 Ai和 Bi写在纸上，其他人不能看见。过了一段时间后，每个人说出自己纸上的数字，然后每个人的目标是求出所有的 AiBi的和模 M的值，最先
2、算出结果的，就是胜利者。 作为一个程序员，你当然有办法编一个程序，以最快的速度算出结果，赢得比赛。 输 入 输入包含 Z组测试数据，输入第一行只包含数字 Z。 随后是测试数据：第一行是一个数字 M(1M45000)。 第二行是数字 H（ 1H45000） 表示参加游戏的人数。接下来 H行，每行两个数 Ai和 Bi（ 1Ai，Bi231） 输 出 对于每组测试数据，输出以下表达式的值： (A1B1+A2B2+.+AHBH)modM. 输 入 样 例 3 16 4 23 34 45 56 36123 1 23748593029382 17 1 318132 输 出 样 例 2 13195 13解 题 思路 （ 1） 取模运算可以与加、减、乘、乘方交换次序； (a+b)%m=a%m+b%m a*b%m=(a%m)*(b%m) ab%m=(a%m)b 解 题 思路 （ 2） 有一类常见的运算，就是求形如的值，一般情况下，我们可以用幂的定义来做：通过乘法的倍乘来实现，需要做 b次乘法和模运算。如果 b比较大时，这样的方法就不行了，本节介绍一种只需要O(log2b)次乘法和模运算的方法。
