10.1.1 除法表达式
gcd递归层数最多4.785lgN + 1.6723, N = max(a, b)
cint gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b);} 10.1.2 无平方因子数
主要讲的是素数的问题.
Eratosthenes 筛法
cmemset(vis, 0, sizeof(vis));for(int i = 2; i <=n ;i++) for(int j = i*2; j <=n; j+= i) vis[j] = 1;
由此一来就可以筛选出素数,不过不是线性筛法,相信佳哥也一定知道...
循环的总次数小于n/2 + n/3 + ... n/n = o(nlogn)
欧拉1734年的结果: 1 + 1/2 + 1/3 + .. 1/n = ln(n+1) + y
允许在 $10^6$ 以内的所有素数.
- 通过素数定理求素数的个数:
PI(x) ~ x/lnx
10.1.3 直线上的点
扩展欧几里德算法求解.
g = gcd(a,b), 方程解为(x0c/g, y0c/g)
cvoid gcd(int a, int b, int& d, int& x, int& y){ if(!b) { d = a; x = 1; y = 0;} else { gcd(b, a%b, d, y, x); y -= x*(a/b); }} 10.1.4 同余模算数
公式
(a+b) mod n = ((a mod n) + (b mod n)) mod n(a-b) mod n = ((a mod n) - (b mod n) + n) mod nab mod n = (a mod n)(b mod n) mod n
乘法取余
cint mul_mod(int a, int b, int n){ a %= n; b %=n; return (int)((long long) a * b % n);} 大整数取MOD
cint big_int(char *n, int m){ int len = strlen(n); int ans = 0; for(int i = 0; i < len; i++) ans = (int)(((long long)ans * 10 + (n[i]-'0')) % m); return ans;} 幂取模
cint pow_mod(int a, int n, int m){ int x = pow_mod(a, n/2, m); long long ans = (long long)x * x % m; if (n % 2 == 1) ans = ans * a % m; return (int) ans;} 模线性方程
有一处没看明白,为何ax-b是n的正整数倍,而不是(a-b)x?
10.2.1 杨辉三角和二项式定理
给定n求(a+b)^n所有项的系数
c memset(C, 0, sizeof(C)); for(int i = 0; i <= n; i++) { C[i][0] = 1; for(int j = 1; j <= n; j++) C[i][j] = C[i-1][j-1] + C[i-1][j]; } - 10-4
提供一种思路,就是大数字的乘除法可以借用素数和指数来表示.
10.2.2 数论中的计数问题
- 10-5
分解质因数
- 10-6 小于n且与n互素的数的个数
欧拉函数
cint euler_phi(int n){ int m = (int) sqrt(n + 0.5); int ans = m; for(int i = 2; i <= m; i++) if(n % i == 0) { ans = ans / i*(i-1); while(n % i == 0) n /= i; } if(n > 1) ans = ans/n * (n-1); return ans;}// 筛法求范围内的欧拉函数 void phi_table(int n, int *phi){ for(int i = 2; i <= n; i++) phi[i] = 0; phi[1] = 2; for(int i = 2; i <= n; i++) if(!phi[i]) for(int j = i; j <= i; j+= i) { if(!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i-1); }} 编码解码
编码解码更多的利用树来构造.
10.2.4 离散概率初步
- 生日的问题
边乘边除
cdouble birthday(int n, int m){ double ans = 1.0; for(int i = 0; i < m ;i++) ans *= (n-1)/n; return 1-ans;} 10.3.1 汉诺塔
利用数学归纳法来证明问题
10.3.2 Fibonacci数列
递推式,1,1,2,3,5,8...
10.3.3 Catalan 数
凸多边形的三角划分数量,车入栈出站方法均是卡特兰数.
计算方法$f(n) = f(2)f(n-1) + f(3)f(n-2) + ... f(n-1)f(2)$
或者
$f(n+1) = (4n-6)/n * f(n)$
1,2,5,14,42,132,429,1430,4862,16796.