数论(二)经典问题和算法.pptVIP

《算法艺术与信息学竞赛》标准课件 数论(二): 经典问题和算法 刘汝佳 问题1: 大整数取余 给一个n位的大整数P和正整数m 求P mod m的值 输入 int n, int m int digit[]：digit[0]为P第首位，digit[n-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位的余数d[i-1]推出第i位的余数d[i] = (d[i-1]*10+digit[i]) mod m 时间复杂度: O(n) 每个d[i]都只使用一次，空间复杂度O(1) 问题2: 模取幂 给出a, n, p, 求an mod p的值 输入 int a int n int p 输出 int d 分析 算法一: 利用公式 an mod p = (an-1 mod p) * a mod p 时间复杂度: O(n) 算法二: 把n写成二进制n = (nknk-1…n0)2 设di为a的2i次方模p的结果, 则 an mod p = (dk^nk) * (dk-1^nk-1) * … 即把nk为1的那些dk乘起来 时间复杂度: O(logn) 分析 设si为数(nknk-1…ni), 则nk = sk 1 从右往左递推 dk = (dk-1 * dk-1) mod p sk = sk-1 1 由于每个数只被用一次, 空间是O(1)的 问题: dk-1*dk-1可能会overflow! (n=105时已经会) 解决方法: 使用更大的整数范围 分析 下面的数据类型LL取决于编译器. gcc使用long long, 而VC++使用__int64 对于其他操作符, 把*d%p替换掉即可 问题3: 求1~n的所有素数 求1~n的所有素数 输入 int n 输出 bool isPrime[]：数i(1=i=n)是否为素数 int prime[]：第i(1=i=π(n+1))个素数 int primeCount：素数总数 分析 假设要求1~100的素数 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(想一想, 为什么) Eratosthenes的筛子 分析 问题：i*j可能超界！ 解决办法： 改用除法判断，并预先判断是否有i2n. 更好的办法是递推求i2, 利用(i+1)2-i2=2i+1, 另设一个变量k=i2 100, 1000, 10000…109内的素数个数分别为：25, 168, 1229, 9592, 78498, 664579, 5761455,用筛法一般最多用来计算107内的素数 优化 枚举过程也可以优化一下 优化一：除了2以外偶数都不是素数，所以每次i可以增加2 优化二：除了2、3以外，素数p除以6的余数只能是1或5，所以可以修改为每次交替增加2, 4 时间优化并不明显, 但空间分别缩小为原来的1/2和1/3 分析 时间复杂度显然为筛的时间复杂度+O(n) 筛的过程不超过n/2+n/3+n/5+… 由公式 得: 筛的过程是nlnlnn的, 总O(nloglogn) 其中B1为Mertens常数0.2614972128… 问题4: 素数判定 给定正整数p 判断p是否为素数 输入 int p 输出 bool isPrime 算法一 朴素的枚举法, 枚举到n1/2为止 任务: 统计1~n的素数个数 n=105时瞬间, n=106时需要数秒 优化 可以利用前面所说的模6优化, 速度为原来的若干倍. 优化后106次一秒之内出解, 107需要约10秒 优化 也可以改成只用素数试除, 速度变快但速度并不是很明显(n=107时约两倍). 其中primes初始化为2和3, 随着循环测试的进行不断更新 Miller-Rabin测试 对于奇数n, 记n=2r*s+1, 其中s为奇数 随机选a(1=a=n-1), n通过测试的条件是 as≡1(mod n), 或者 存在0=j=r-1使得a(2^j)*s≡-1(mod n) 素数对于所有a通过测试, 合数通过测试的概率不超过1/4 注意: 先要判断此数本身是否为a的倍数 Miller-Rabin测试 能通过a=2的最小合数是2047=23*89 能通过