数学问题
《算法笔记》第五章 数学问题
最大公约数和最小公倍数
求解最大公约数的方法一般为欧几里得法，即辗转相除法。0和任意整数的最大公约数都是整数本身。
1
2
3
4
| int gcd(int x, int y) {
if(y==0) return x;
return gcd(y, x % y);
}
|
最小公倍数的求解方法是在求解最大公约数的基础上进行的，最小公倍数的求解方法未a*b/d，d就是最大公约数。为了避免超出类型范围，一般为a / d * b。
素数
素数，也叫做质数是指除了1和本身之外，不能被任意的整数整除的数字。
合数是指可以被除了1和本身之外的数字整除的数字。
特殊的是1，1既不是素数，也不是合数。
判断素数
假设数字n可以被k整除：n % k == 0，我们当然可以遍历从2开始到n-1的所有值检查是否可以整除。
实际上，可以缩小判断范围，考虑平方根，sqrt(n)*sqrt(n) == n，所有可以整除n的第一个数字，一定是<= sqrt(n)，因此我们只需要遍历从2开始到sqrt(n)。
1
2
3
4
5
6
7
8
9
| bool isPrime(int x) {
int sqr = sqrt(x);
for(int i = 2; i <= sqr; ++i) {
if(n % i == 0) {
return false;
}
}
return true;
}
|
获取素数表
我们当然可以判断每一个数字是否是素数获得素数表，但是这样效率较低。
可以考虑使用埃式筛选法：
如果一个数字i是素数，就把它所有的后续整倍数筛选出去。如果一个数没有被筛选出去，那它就是素数。初始化默认2是素数。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int prime[maxn];
int pNum = 0;
bool isPrime[maxn] = {true};
void findPrime() {
for(int i = 2; i < maxn; ++i) {
if(isPrime[i]) {
prime[pNum++] = i;
for(int j = 2; i * j < maxn; ++j) {
isPrime[i * j] = false;
}
}
}
}
|
质因子分解
把一个数字n分解为多个质数的乘积形式。
首先通过获取质数表，我们可以获得所有的候选质数，然后判断各个质数是否是数字n的因子。
同样的，类似于判断质数的方法，数字n的>=sqrt(n)的质因子至多有一个，<sqrt(n)的质因子可以有多个，因此，我们可以先寻找所有<sqrt(n)的质因子，之后如果发现乘积不为数字n，则继续计算。
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
| struct factor {
int x, cnt;
} fac[10];
findPrime();
int sqr = sqrt(n);
int num;
for(int i = 0; i < pNum && primes[i] <= sqr; ++i) {
if(n % prime[i] == 0) {
fac[num].x = prime[i];
fac[num].cnt = 0;
while(n % prime[i] ==0) {
n = n / prime[i];
fac[num].cnt++;
}
num++;
}
if(n==1) break;
}
if(n != 1) {
fac[num].x = n;
fac[num].cnt = 1;
}
|
大整数运算
大整数的存储
对于过于大的整数，比如1000位的整数，不能再使用基本类型存储，因此考虑使用结构体进行存储。
1
2
3
4
5
6
7
8
| struct bign {
int d[1000];
int len;
bign() {
memset(d, 0, sizeof(d));
len = 0;
}
}
|
需要记住我们使用从低位到高位的存储办法。因此，在读入大整数的时候，对于读入的大整数可以先考虑使用char[]保存，然后逆位赋值给bign。同理，bign和bign的比较，同样是从len-1开始比较。
大整数的四则运算
大整数的加法，从最低位开始相加，如果大于10就进位（除以10），余数在当前位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bign add(bign a, bign b) {
bign c;
int carry = 0;
int tmp;
for(int i = 0; i < a.len || i < b.len; ++i) {
tmp = a.d[i] + b.d[i] + carry;
c.d[i] = tmp % 10;
c.len++;
carry = tmp / 10;
}
if(carry != 0) {
c.d[len++] = carry;
}
return c;
}
|
大整数的减法，与加法的一个很大区别是，需要首先判断两个大整数的大小，总是使用大整数减去小整数，对于结果是负数的情况额外输出负号即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bign sub(bign a, bign b) {
bign c;
for(int i =0; i < a.len || i < b.len; ++i) {
if(a.d[i] - b.d[i] < 0) {
a.d[i + 1]--;
a.d[i] += 10;
}
c.d[len++] = a.d[i] - b.d[i];
}
while(c.len > 1 && c.d[len - 1] == 0) {
c.len--;
}
return c;
}
|
大整数与int的乘法，类似于大整数的加法，从低位到高位，将int与大整数的某一位相乘，结果加上进位，然后个位保留作为该位结果，更高位作为进位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| bign mult(bign a, int b) {
bign c;
int tmp, carry = 0;
for(int i = 0; i < a.len; ++i) {
tmp = a.d[i] * b + carry;
c.d[len++] = tmp % 10;
carry = tmp / 10;
}
while(carry != 0) {
c.d[len++] = carry % 10;
carry /= 10;
}
return c;
}
|
大整数与int的除法，每一步都是上一步的余数乘以10，加上当前位与除数相除，结果作为当前位，余数留到下一位。除法需要从高位开始操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bign divide(bign a, int b) {
bign c;
c.len = a.len;
int tmp, carry = 0;
for(int i = a.len - 1; i >= 0; --i) {
tmp = carry * 10 + a.d[i];
a.d[i] = tmp % b;
carry = tmp / b;
}
while(c.len > 1 && c.d[len - 1] == 0) {
c.len--;
}
return c;
}
|
组合数
关于问题，求n!有几个质因子p？
可以记住一个式子，n!中有\(\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+\dots\)的质因子p。
1
2
3
4
5
6
7
8
| int cal(int n, int p) {
int ans = 0;
while(n) {
ans += n / p;
n /= p;
}
return ans;
}
|
上面答案的一个变形是求解n!会有末尾0的个数，本质上等于求有多少个2和5的组合的个数，又因为质因子2的数量多于5，因此直接求解n!有多少个质因子5即可。
求解组合数\(C_{n}^{m}\)，如果直接使用公式\(\frac{n!}{m!(n-m)!}\)可能超界限，可以考虑使用公式\(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}\)。
1
2
3
4
5
6
7
8
9
10
| long long res[67][67] = {0};
long long C(long long n, long long m) {
if(m==0 || n==m) {
return 1;
}
if(res[n][m] != 0) {
return res[n][m];
}
return res[n][m] = C(n-1, m) + C(n-1, m-1);
}
|