ACM数论2.ppt

数论 来自天津大学等学校的培训材料 初等数论的概念 整除性和约数： 假设d和a是整数，d|a（读作d整除a），意味着存在某个整数k，有a=kd。 如果d|a，并且d≥0，则称d是a的约数。 每个整数a都可以被其平凡约数1和a整除，a的非平凡约数也成为a的因子。 快速幂 3 ^ 999= 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)= (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3 这样只要做16次乘法。即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。 我们发现，把999转为2进制数：1111100111，其各位就是要乘的数。这提示我们利用求二进制位的算法（其中mod是模运算）： 快速幂 NumberType optimized_pow_n(NumberType x, unsigned int n) { NumberType pw = 1; while (n 0) { if (n 1) // n 1 等价于 (n % 2) == 1 pw *= x; x *= x; n = 1; // n = 1 等价于 n /= 2 } return pw; } 初等数论的概念 素数和和数 对于某个整数a1，如果它仅有平凡约数1和a则称p是素数。否则p是合数。 可以证明素数有无限多个。 筛法求素数。 int vis[1000000]={1, 1}; int prime[1000000]; int prime_count = 0; void create_prime(int n) { int i, j, m; m = (int)sqrt(n + 0.5); for(i = 2; i = m; i++) if(!vis[i]){ prime[prime_count++] = i; for(j = i * i; j = n; j+=i) vis[j] = i; } } 初等数论概念 除法定理，余数和同模 除法定理：对任意整数a和任意正整数n，存在唯一的整数q和r，使得a=qn+r，其中0≤rn。 值q称为除法的商，值r=a(mod n)称为除法的余数。 根据整数模n所得的余数，可以把整数分成n个等价类。包含整数的模n等价类为：[a]n={a+kn| k∈Z} 常见数列 1.Fibonacci数列 2.卡特兰数 ?h(1)＝1,h(0)=1 ?h(n)=C(2n,n)/(n+1) (n=1,2,3,...) 3.错排数 n个有序的元素应有n ！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则称这个排列为错排。 M(1)=0,M(2)=1 M(n)=(n-1)[M(n-2)+M(n-1)] …………………… 给定N个节点，能构成h(N)种不同的二叉树 /showproblem.php?pid=1005 方法一 循环出现？ 方法二 矩阵幂 fn+1 A B fn fn 1 0 fn-1 另：/problem?id=3070 初等数论的概念 公约数与最大公约数 d是a的约数并且也是b的约数，则d是a和b的公约数。 两个不同时为0的整数a和b的最大公约数表示为gcd(a, b)。 初等数论的概念 gcd(a, b) 的性质： 定理：如果a，b是不全为0的任意整数，则gcd(a, b)是a与b的线性组合{ax+by:x,y∈Z}中的最小正元素。 推论1：对于任意整数a，b，如果d|a并且d|b，则d|gcd(a, b)。 推论2：对于所有整数a和b以及任意非负整数n，gcd(an, bn)=n*gcd(a,b)。 推论3：对所有正整数n，a和b，如果n|ab并且gcd(a, n)=1，则n|b。 初等数论的概念 互质数： 如果两个整数a与b只有公因数1，即如果gcd(a, b)=1，则a与b称为互质数。 定理：对任意整数a，b和p，如果gcd(a, p)=1且gcd(b, p)=1，则gcd(ab, p) = 1。 初等数论概念 唯一因子分解 唯一质因子分解定理：合数a仅能以一种方式，写成如下的乘积形式： a=p1e1p2e2…prer 其中pi为素数，p1p2…pr，且ei为