《数论(二)经典问题和算法》由会员分享，可在线阅读，更多相关《数论(二)经典问题和算法（58页珍藏版）》请在金锄头文库上搜索。
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推出第i 位的余数di = (di-1*
2、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 = 1);问题3: 求1n的所有素数 求1n的所有素数 输入
3、 int n 输出 bool isPrime：数i(1n. 更好的办法是递推求i2, 利用(i+1)2 -i2=2i+1, 另设一个变量k=i2 100, 1000, 10000109内的素数个数分别 为：25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534 用筛法一般最多用来计算107内的素数优化 枚举过程也可以优化一下 优化一：除了2以外偶数都不是素数，所以每 次i可以增加2 优化二：除了2、3以外，素数p除以6的余数只 能是1或5，所以可以修改为每次交替增加2, 4 时间优化并不明显, 但空间分别缩小为原来 的1/2和1/3分析 时间
4、复杂度显然为筛的时间复杂度+O(n) 筛的过程不超过n/2+n/3+n/5+ 由公式 得: 筛的过程是nlnlnn的, 总O(nloglogn) 其中B1为Mertens常数0.2614972128问题4: 素数判定 给定正整数p 判断p是否为素数 输入 int p 输出 bool isPrime算法一 朴素的枚举法, 枚举到n1/2为止 任务: 统计1n的素数个数 n=105时瞬间, n=106时需要数秒for(i = 2; i * i = 1; r+; LL k = pow_mod(a, s, n); if(k = 1) return true; for(j = 0; j b时 a和b均为
5、偶数, gcd(a,b)=2*gcd(a/2,b/2) a为偶数, b为奇数, gcd(a,b)=gcd(a/2,b) 如果a和b均为奇数, gcd(a,b)=gcd(a-b,b) 不需要除法, 只需减法和右移, 适合大整数Euclid算法 测试: 求1= 1; c = 1; else c=0;if(!(b d = 1; else d=0;if(c 问题10: 求1n的欧拉函数 给正整数n, 求1n每个数的欧拉函数值 输入 Int n 输出 Int phi分析 n的每个素因子p对n的phi值都有(1-1/p)的贡 献, 因此可以借助素数筛法实现, 但是必须 从p开始而不是p*p开始, 因此更接
6、近nlnlnn 不需要额外的isPrime标志, 直接判断目前的 phi. 如果为0, 说明为素数 先检查j的phi函数值. 如果为0, 说明从来没 有被筛过, 赋初值j. 筛的时候顺便把phij乘以(1-1/p), 注意先除 再乘避免overflow分析 可以顺便求出素数表, 只需要在if(!phii)时 先进行primesprimeCount+ = i即可.phi1 = 1; for(i = 2; i x, 其中 xj代表满足ei=j的最小i(可能有多个i, 如a=1 时)m = (int)ceil(sqrt(n); v = inverse(pow_mod(a, m, n), n); e = 1; x1 = 0; for(i = 1; i m; i+)e = e * (LL)a % n; if(!x.count(e) xe = i; for(i = 0; i m; i+)if(x.count(b) return i*m+xb;b=b * (LL)v % n; 问题12: 模平方根 给整数a, n 求满足x2a(mod n)的所有根 输入 Int a, int n 输出 Int d: 解的个数 Int x: 所有解分析 类似于实数方程, 可能有三种情况: 无解, 两 等根和两异根 下面介绍Shank算法
