1、 算法艺术与信息学竞赛 标准课件数论 (二 ): 经典问题和算法刘汝佳问题 1: 大整数取余 给一个 n位的大整数 P和正整数 m 求 P mod m的值 输入 int n, int m int digit： digit0为 P第首位， digitn-1末位 输出 int d： P mod m的值分析 公式一 : (a*b) mod m = (a mod m) * (b mod m) mod m 公式二 : (a+b) mod m = (a mod m) + (b mod m) mod m 注意 : 在两个公式中 , 都需要在最后对 m取模分析 由公式 , 可以由前 i-1位的余数 di-1推
2、出第 i位的余数 di = (di-1*10+digiti) mod m 时间复杂度 : O(n) 每个 di都只使用一次，空间复杂度 O(1)d = 0;for(i = 0; i 1 由于每个数只被用一次 , 空间是 O(1)的 问题 : dk-1*dk-1可能会 overflow! (n=105时已经会 ) 解决方法 : 使用更大的整数范围分析 下面的数据类型 LL取决于编译器 . gcc使用long long, 而 VC+使用 _int64 对于其他操作符 , 把 *d%p替换掉即可LL ans = 1, d = a % p;doif(n d = (d * d) % p;while(n
3、= 1);问题 3: 求 1n的所有素数 求 1n的所有素数 输入 int n 输出 bool isPrime：数 i(1=i=n)是否为素数 int prime：第 i(1=i=(n+1)个素数 int primeCount：素数总数分析 假设要求 1100的素数 2是素数 , 删除 2*2, 2*3, 2*4, , 2*50 第一个没被删除的是 3, 删除 3*3, 3*4, 3*5,3*33 第一个没被删除的是 5, 删除 5*5, 5*6, 5*20 得到素数 p时 , 需要删除 p*p, p*(p+1), p*n/p, 运算量为 n/p-p, 其中 p不超过 n1/2(想一想 , 为什么 )
