数学知识集锦

  1. 用一个平面截球而得到球的一部分叫做球缺, 球缺是实体，它的体积公式为：
    V = π h² (3 * r - h) / 3;
    r表示球的半径，h表示球缺的高。

球冠是球面的一部分，是用平面去截球面而得到的一部分, 这个平面截球面所得的圆叫做球冠的底，垂直于截面的球的直径被这截面截得的线段的长叫做球冠的高。
球冠的面积公式是S = 2 π r * h。

  1. 欧拉函数: ϕ(n) 1~n中与n互质的数的个数

令n = p1^r1 p2^r2…pk^rk
则ϕ(n)=n(1-1/p1)(1-1/p2)…*(1-1/pk)
其中p1, p2……pn为n的所有质因数，n是不为0的整数。

欧拉函数是积性函数:

  1. 若m,n互质，ϕ(mn) = ϕ(m) * ϕ(n)
  2. 当n为奇质数时，ϕ(2n) = ϕ(n)
  3. 若n为质数, 则 ϕ(n) = n - 1

乘法逆元 

1
2
3
4
5
6
7
8
9
10
11
12
13
/* a * x = 1 (mod p)   x称为ａ关于１模p的乘法逆元,求x
 *
 * 方法一：扩展欧拉定理
 * a * x = 1 (mod p)  => a * x + p * y = 1
 * 利用扩展欧几里得法求得ｘ和ｙ，其中x为a关于１模ｐ乘法逆元
 *
 * 方法二：费马小定理
 * 费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡ 1（mod p）  (p是质数)
 *    a ^ (p - 1) = 1 (mod p)
 * => a * a ^ (p - 2) = 1 (mod p)
 * 令x = a^-1, x = a ^ (p - 2)(mod p)
 * 利用快速幂求得x
 */

阅读全文 >>

扩展欧几里得 

1
2
3
4
5
6
7
8
9
10
当b = 0时，gcd(a, b) = a, 此时x = 1, y = 0
当a > b时，设a * x1 + b * y1 = gcd(a, b);
             b * x2 + (a % b) * y2 = gcd(b, a % b);
gcd(a, b) = gcd(b, a % b);
所以a * x1 + b * y1 = b * x2 + (a % b) * y2;
=> a * x1 + b * y1 = b * x2 + (a - [a / b] * b) * y2;   []表示取整
=> a * x1 + b * y1 = a * y2 + b * (x2 - [a / b] * y2);
=> x1 = y2,  y1 = x2 - [a / b] * y2

此时得出x1和y1的值基于x2和y2,因而可以将每次a * x2 + b * y2 = gcd(b, a % b)的x2、y2的值代入求得x1和y1, 多次递归后b = 0，x = 1, y = 0,　最终求得x和y的值，即a * x + b * y = gcd(a, b) 的方程组的解

阅读全文 >>

最大公约数 

1
2
3
4
5
6
7
//辗转相除法
 a = 6 b = 4
 a - b * k = n
 a % b = n
 6 - 4 * 1 = 2   gcd(b, a % b) => a = 4(b) b = 2(a % b)
 4 - 2 * 1 = 2   => a = 2 b = 2
 2 - 2 * 1 = 0   => a = 2 b = 0   当ｂ＝０时,得到最大公约数2

阅读全文 >>

并查集 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
using namespace std;

const int SIZE = 100;

int father[SIZE], height[SIZE];   //father记录每个元素的上级，height记录等级

void init(int n){
	for(int i = 0; i < n; i++){  
		father[i] = i;    //初始时，每个元素的上司是自己
		height[i] = 1;    //初始等级为1
	}
}

int find(int v){
	return father[v] = father[v] == v ? v : find(father[v]);   //找到元素的最高一级指挥官
}

void join(int x, int y){
	x = find(x);
	y = find(y);
	if(height[x] < height[y])    //把等级低的放等级高的下面
		father[x] =father[y];
	else{
		father[y] = x;               // 如果后者等级高，那么将等级低的归自己管
		if(height[x] == height[y])   //如果两者等级相等，那么当把同等级的归自己管，而自己等级需+1
			height[x]++;
	}
}

int main(){
	int n, m;
	cin >> n >> m;
	int x, y;
	init(n);   //初始化等级
	for(int i = 1; i <= m; i++){
		cin >> x >> y;      //输入有关联的两个人
		join(x, y);         //加入到集合中来 
	}
	for(int i = 1; i <= n; i++)
		cout << i << " ";
	cout << endl;
	for(int i = 1; i <= n; i++)
		cout << find(i) << " ";
	return 0;
}

矩阵快速幂 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 利用矩阵快速幂求斐波那切数列
 F[i] = 1 * F[i - 1] + 1 * F[i - 2] 
 F[i - 1] = 1 * F[i - 1] + 0 * F[i - 2];

 -       -    -   -     -        -
|  F[i]	  | =| 1 1 | * | F[n - 1] | 
|F[i - 1] |  | 1 0 |   | F[n - 2] |
 -       -    -   -     -        - 
 -       -    -   - ^(n - 1) -    -
|  F[i]	  | =| 1 1 |        | F[1] | 
|F[i - 1] |  | 1 0 |   *    | F[0] |
 -       -    -   -          -    - 

      -   -  
 A = | 1 1 |
     | 1 0 |
      -   - 

 也就是使用矩阵快速幂求出A的n - 1次方，F[1] = 1, F[0] = 0,求得的矩阵为A'(2 * 1)，数列第ｎ个的值为A'[0][0]

阅读全文 >>

埃氏筛法

埃氏筛法：首先用一张表把1～n的所有数表示出来，其中2是最小的素数，将表中所有2的倍数划去，表中剩余的最小数字为3，它不能被更小的数整除，因而它是素数，将3的倍数从表中划去，依次类推，就能枚举n以内的素数, 时间复杂度O(nlognlogn)

阅读全文 >>

快速幂 

1
2
3
4
x ^ n = ((x^2)^2)...
x ^ n = x^(2^k1) * x^(2^k2)...
x^22 = x^2 * x^4 * x^16
x^21 = x * x^4 * 2^16  //21的二进制为10101，在１处进行res *= x;

阅读全文 >>

|