数学问题
发表于：2024-02-03 | 分类： 数据结构与算法

基础算法

位运算以及优化技巧

快读

1
2
3
4
5
6
7
8
9
std::ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
	return x * f;
}

位运算

1
2
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

一、高精度

1.高精度加法

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
#include<iostream>
#include<string>
using namespace std;
//高精度加法计算
const int N = 510;
int a[N], b[N], c[N];
int main()
{
    string str1;
    string str2;
    cin >> str1;//输入第一个数
    cin >> str2;//输入第二个数
    for (int i = 0; i < str1.size(); i ++)//逆序输入
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)//逆序输入
        b[str2.size()-1 - i] = str2[i] - '0';
    int len = max(str1.size(), str2.size());
    for (int i = 0; i < len; i ++){
        c[i] += a[i] + b[i];
        c[i+1] += c[i] / 10;//若大于10，进1
        c[i] %= 10;
    }
    len += 1;
    if (c[len-1] == 0 && len > 1)
        len -= 1;
    for (int i = 0; i < len; i ++)
        cout << c[len-1-i];//逆序输出数组
    return 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
#include<iostream>
#include<String>
using namespace std;
const int N=510;
int a[N],b[N],c[N];
int main()
{
string s1, s2;
cin >> s1 >> s2;    //输入两个数字
//判断相减之后是否为负数
if (s1.size() < s2.size() || s1.size() == s2.size() && s1 < s2) {
    swap(s1, s2);    //交换s1和s2，保证使用s1-s2
    cout << "-";
}
int len = max(s1.size(), s2.size());
for (int i = 0; i < s1.size(); ++i) {
    a[s1.size() - 1 - i] = s1[i] - '0';    //逆序输入
}
for (int i = 0; i < s2.size(); ++i) {
    b[s2.size() - 1 - i] = s2[i] - '0';    //逆序输入
}
//处理相减
for (int i = 0; i < len; ++i) {
    if (a[i] < b[i]) { //不够减向上借一位
        a[i + 1]--;
        a[i] += 10;
    }
    c[i] = a[i] - b[i];
}
//删除前导0
while (c[len - 1] == 0 && len > 1) {
    len--;
}
for (int i = len - 1; i >= 0; --i) {   //逆序输出
    cout << c[i];
}
	
	
	
	return 0;
}

3.高精度乘低精度

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
#include<iostream>
#include<string>
using namespace std;
const int N=510;
int a[N],b,c[N];
int main()
{
	string s;
	cin>>s>>b;//输入大数字 小数字
	int len=s.size();
	for(int i=0;i<len;i++)
	{
		a[len-1-i]=s[i]-'0';//逆序输入
	}
	//处理相乘
	for(int i=0;i<len;i++)
	{
		c[i]+=a[i]*b;
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	//求出数组最终长度
	while(c[len]>0)
	{
		c[len+1]+=c[len]/10;
		c[len]%=10;
		len++;
	}
	//删除前导0
	while(c[len-1]==0&&len>1)
	{
		len--;
	}
	for(int i=len-1;i>=0;i--)//逆序输出
	{
		cout<<c[i];
	}
	return 0;
}

4.高精度乘高精度

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
#include<iostream>
#include<string>
using namespace std;
const int N=510;
int a[N],b[N],c[N];
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	for(int i=0;i<s1.size();i++)
	{
	    a[s1.size()-1-i]=s1[i]-'0';//逆序输入
	}
	for(int i=0;i<s2.size();i++)
	{
		b[s2.size()-1-i]=s2[i]-'0';//逆序输入
	}
	//处理相乘
	for(int i=0;i<s1.size();i++)
	{
		for(int j=0;j<s2.size();j++)
		{
			int k=i+j;
			c[k]+=a[i]*b[j];
			c[k+1]+=c[k]/10;
			c[k]%=10;
		}	
	}
	//判断进位进到哪里，两个数相乘，位数最多是x+y位，所以从x+y+1位那里开始判断
	int len=s1.size()+s2.size()+1;
	if(c[len-1]>0)len++;
	//删除前导0
	while(c[len-1]==0&&len>1)
	{
		len--;
	}
	for(int i=len-1;i>=0;i--)
	{
		cout<<c[i];//逆序输出
	}	
	return 0;
}

5.低精度除法高精商

a除以b，要求输出小数点后n位

1
2
3
4
5
6
7
8
9
10
11
12
13
int a, b, n, c[100];
c[0] = a / b;   //整数部分
int t = a % b;
for (int i = 1; i <= n; ++i) {
    c[i] = t * 10 / b;
    t = t * 10 - c[i] * b;
}
//先输出小数点前的数字以及小数点
cout << c[0] << '.';
//然后再来输出小数点后面的数
for (int i = 1; i <= n; ++i) {
    cout << c[i];
}

6.高精度除法低精度商

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
//除数用s1存放，被除数用int b存放，余数用int t存放，商用s2存放
string s1, s2;
int b, t, x;
cin >> s1 >> b;
//高精度除法用正序转存s1
for (int i = 0; i < s1.size(); ++i) {
    a[i] = s1[i] - '0';
}
//商暂时存在数组c中，长度存在int x中
t = x = 0;
//代入计算的时候要注意余数t的参与
for (int i = 0; i < s1.size(); ++i) {
    c[i] = (t * 10 + a[i]) / b; //记得加上上一个数作除法之后留下的余数
    t = (t * 10 + a[i]) % b;
}
//处理前导0
while (c[x] == 0 && x < s1.size()) {
    x++;
}
//将商存到s2中
for (int i = x; i < s1.size(); ++i) {
    s2 += c[i] + '0';
}
//输出商和余数
cout << s2 << ' ' << t;

二、分数计算

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a,int b)//最大公约数
{
	if(b==0)return a;
	return gcd(b,a%b);
}
//分数运算
struct Frac//分数
{
	int up;//分子
	int down;//分母
};
//约分
Frac reduction(Frac result)
{
	if(result.down<0)//分母为负数，分子分母变相反数
	{
		result.up=-result.up;//符号位放在分母上
     	result.down=-result.down;
	}
	if(result.up==0)//分子为0
	{
		result.down=1;//分母为1
	}
	else {
		int d=gcd(abs(result.up),abs(result.down));//约分
		result.up/=d;
		result.down/=d;
	}
	return result;
}
//乘法
Frac multi(Frac f1,Frac f2)
{
	Frac result;
	result.up=f1.up*f2.up;
	result.down=f1.down*f2.down;
	return reduction(result);
}
//除法
Frac divide(Frac f1,Frac f2)
{
		Frac result;
	result.up=f1.up*f2.down;
	result.down=f1.down*f2.up;
	return reduction(result);
}
//加法
Frac add(Frac f1,Frac f2)
{
		Frac result;
	result.up=f1.up*f2.down+f1.down*f2.up;
	result.down=f1.down*f2.down;
	return reduction(result);
}
//减法
Frac minu(Frac f1,Frac f2)
{
	Frac result;
		result.up=f1.up*f2.down-f1.down*f2.up;
	result.down=f1.down*f2.down;
	return reduction(result);
}
//输出
void show(Frac r)
{
	r=reduction(r);
	if(r.down==1)printf("%lld\n",r.up);
	else if(abs(r.up)>r.down)
	{
		printf("%d %d/%d\n",r.up/r.down,abs(r.up)%r.down,r.down);//假分数表示形式
	}
	else printf("%d/%d\n",r.up,r.down);
}
int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	Frac f,e,r;
	f.up=a;e.up=c;
	f.down=b;e.down=d;
	show(f);
	show(e);
	r=add(f,e);
	show(r);
	r=minu(f,e);
		show(r);
	r=multi(f,e);
		show(r);
	r=divide(f,e);
		show(r);
	return 0;
}

三、前缀和

1.一维前缀和

dp[i]表示从下标1开始到下标i的一维数组元素之和，若计算区间[a,b]的数组元素之和，其中递推式sum=dp[j]-dp[i-1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
const int N=100010;
int arr[N],dp[N];//dp[i]表示从下标1开始到下标i的数组元素之和
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1]+arr[i];//计算前缀和
	}
	
	
	return 0;
}

2.二维前缀和

s(i,j)表示从（1,1)开始到（i，j)位置的二维数组所有元素之和，其中递推式为s(i,j)+=s(i-1,j)+s(i,j-1)-s(i-1,j-1),则从（a+1,b+1)到（c，d)的和为s[a,b]+s[c,d]-s[a,d]-s[b,c].

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
48
49
#include<iostream>
#include<string>
using namespace std;
//二维前缀和
//s[i][j]表示从arr[1][1]到arr[i][j]的和
int n,l,r,t,arr[605][605],count,sum[605][605];
/*
4 16 1 6
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
*/
bool judge(int x,int y)
{
    double sumval=0;int num=0;
	int left=max(1,x-r),right=min(n,x+r);//左右边界
	int down=max(1,y-r),up=min(n,y+r);//上下边界
	sumval = sum[right][up] - sum[right][down-1] - sum[left-1][up] + sum[left-1][down-1];
	num=(right-left+1)*(up-down+1);
	double ave=sumval*1.00/num;
	if(ave<=t)return true;
	return false;
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>l>>r>>t;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>arr[i][j];//读入数据
			sum[i][j]=arr[i][j];
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] ;//计算前缀和
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
		    if(judge(i,j))count++;
		}
	}
	 
	  cout<<count<<endl;
	return 0;
}

四、差分

差分是求前缀和的逆操作，对于原数组a[n],构造出一个b[n]数组中，使a[n]为b[n]的前缀和。一般用于快速对整个数组进行操作，比如将a数组中[l,r]部分的数据全部加上c.使用暴力的方法，则时间复杂度至少为O（n),而使用差分算法时间复杂度降低到O（1）.

1.一维差分
创建一数组b，使得数组a为数组b的前缀和，数组b为数组a的差分

构造方法：b[i] = a[i] - a[i - 1]

此处使用了一个虚拟的构造方式(在数组一个位置加上一个数，那么在它的下一个位置减去这一数)

应用：对于a数组的任意区间[l, r]，令其加上一个数，而不改变其它值

b[l] += c, b[r + 1] -= c

差分操作和前缀和一样数组下标都从1开始。

b[l]+c后，l后面的数组都会加c。r后面的数据也会被改变，要改回来就得b[r+1]-c.

模板题如下

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
48
输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数序列。
接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。输出格式
共一行，包含 n 个整数，表示最终序列。数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2
#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N],b[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ )cin>>a[i];//读入数据
 
    for (int j = 1; j <= n; j ++ )
    {
        b[j]=a[j]-a[j-1];//进行差分
    }
    while (m -- )
    {
        int l,r,c;
        cin>>l>>r>>c;
        b[l]=b[l]+c;
        b[r+1]=b[r+1]-c;
    }
    int sum=0;
    for (int i = 1; i <= n; i ++ )
    {
        
        sum=sum+b[i];
    cout<<sum<<" ";
    }
    return 0;
}

2.二维差分
直接得出公式b[i][j] += c, b[i + 1][j] -= c, b[i][j + 1] -= c, b[i + 1][j + 1] += c
每次对b数组执行以上操作，等价于：

1
2
3
for(int i=x1;i<=x2;i++)
  for(int j=y1;j<=y2;j++)
    a[i][j]+=c;

模板题如下

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。输入格式
第一行包含整数 n,m,q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            insert(i, j, i, j, a[i][j]);      //构建差分数组
        }
    }
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //二维前缀和
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
           cout<<b[i][j];
        }
        cout<<endl;
    }
    return 0;
}

五、二分

整数二分

对lower_bound来说，它寻找的就是第一个满足条件“值大于等于x”的元素的位置；对

upper_bound函数来说，它寻找的是第一个满足“值大于 x”的元素的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;//左加右减
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;//如果下方else后面是l则这里加1
if (check(mid)) l = mid;
else r = mid - 1;//左加右减
}
return l;
}

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
12
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}

六、排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort(int q[], int l, int r)
{
//递归的终止情况
if (l >= r) return;
//选取分界线。这里选数组中间那个数
int i = l - 1, j = r + 1, x = q[l + r >> 1];
//划分成左右两个部分
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
//对左右部分排序
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

边界问题

因为边界问题只有这两种组合，不能随意搭配

1
2
3
4
5
x不能取q[l]和q[l+r>>1];
quick_sort(q,l,i-1),quick_sort(q,i,r);

x不能取q[r]和q[(l+r+1)>>1];
quick_sort(q,l,j),quick_sort(q,j+1,r);

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge_sort(int q[], int l, int r)
{
//递归的终止情况
if (l >= r) return;
//第一步：分成子问题
int mid = l + r >> 1;
//第二步：递归处理子问题
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
//第三步：合并子问题
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
//第四步：复制回原数组
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

七、数学问题

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll
ll binaryPow(ll a,ll b)//计算a^b
{
   ll ans=1;
   while(b)
   {
   	if(b&1)ans*=a;//如果b的二进制末尾是1或者b%2==1,即b是奇数
    b>>=1;//将b的二进制右移一位，即b=b>>1或b/=2;
    a*=a;
   }
   return ans;	
}

素数筛法

1.朴素筛法

1
2
3
4
5
6
7
8
9
10
bool isprime(int n)
{
	if(n<=1)return  false;
		for(int i=2;i<=sqrt(n);i++)
		{
			if(n%i==0)return false;
		}
		
	return true;
}

2.埃氏（Eratosthenes）筛法

假设要筛2-n内的素数，则先将2的倍数从里面剔除，再将3的倍数从里面剔除，以此类推……时间复杂度为O（nloglogn），已经非常接近线性了。

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
#include<iostream>
using namespace std;
//素数表获取
//埃式筛法
const int maxn=101;
int prime[maxn],pnum=0;//数组来记录素数元素，pnum来记录素数个数
bool p[maxn];//素数判断 false 则说明为素数，否则不为素数
void find_prime()
{
	for(int i=2;i<maxn;i++)
	{
		if(p[i]==false)
		{
			prime[pnum++]=i;//记录素数
			for(int j=i;j<maxn;j+=i)//将素数的倍数标记为非素数
			{
				p[j]=true;
			}
		}
	}
}
int main()
{
	find_prime();
	for(int i=0;i<pnum;i++)
	{
		cout<<prime[i]<<" ";
	}
	return 0;
}

3.欧拉（Euler）筛法

欧拉筛法是埃氏筛法的改进，埃氏筛法终究会出现一个数被多个数筛掉的情况。例如因为120 = 2^3 x 3 x 5，因为2，3，5是120的质因子，所以120会被2筛一次，被3筛一次，被5筛一次，共3次。

而欧拉筛法保证了每一个合数都被其最小质因子筛去，保证不会重复筛除。故遍历一次就好，时间复杂度为O（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
26
27
28
29
30
31
#include<iostream>
using namespace std;
//欧拉筛法
const int N=100;
bool p[N];//素数判断 false为素数 
int prime[N],pnum=0;//数组记录素数元素，pnum记录素数个数
void find_prime()
{
	for(int i=2;i<=N;i++)
	{
		if(p[i]==false)
		{
			prime[pnum++]=i;
		}
			for(int j=0;j<pnum&&i*prime[j]<=N;j++)//防止数组越界
			{
				p[i*prime[j]]=true;//最小质因子筛合数
				if(i%prime[j]==0)break;
			}
	}
}
int main()
{	
	find_prime();
	for(int i=0;i<pnum;i++)
	{
		cout<<prime[i]<<" ";
	}
	
	return 0;
}

4、试除法分解质因子

1
2
3
4
5
6
7
8
9
10
11
12
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}

组合数求解

公式：
$$
C_n^m=1(m=0或m=n)\
c_n^m=c_{n-1}^m+c_{n-1}^{m-1}(n>m>0)
$$

所以，我们可以使用动态规划来求解组合数，直接上代码。

1
2
3
4
5
6
7
8
9
//初始化
for (int i = 0; i <= n; ++i) {
    dp[i][i] = dp[i][0] = 1;
}
for (int i = 0; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
    }
}

观察到每一行的组合数都只需要用到上一行组合数的数值，所以可以进行状态压缩，注意倒序处理。

1
2
3
4
5
6
for (int i = 0; i <= n; ++i) {
    for (int j = i; j >= 0; --j) {    //倒序处理
        if (j == i || j == 0) dp[j] = 1;
        else dp[j] = dp[j] + dp[j - 1];
    }
}

进制转换

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
#include<iostream>
#include<map>
//进制转化
using namespace std;
map<char,int>mp1;
map<int,char>mp2;
int num,temp;
char ans[1000];
int main()
{
	for(int i=0;i<10;i++)
	{
		mp1[i+'0']=i;
		mp2[i]=i+'0';
	}
	for(char i='A';i<='F';i++)
	{
		mp1[i]=i-'A'+10;
		mp2[i-'A'+10]=i;	
	}
	int d;//初始进制
	cin>>d;
	string str;//读入数据
	cin>>str;
	for(int i=0;i<str.size();i++)
	{
		//转化为10进制
		temp=temp*d+mp1[str[i]];
	}
	int a;//转化后的进制
	cin>>a;
	while(temp)
	{
		ans[num++]=mp2[temp%a];
		temp/=a;
	}
	for(int i=num-1;i>=0;i--)
	{
		cout<<ans[i];
	}
	
	return 0;
}

最大公约数与最小公倍数

辗转相除法（欧几里得算法）最大公约数

时间复杂度为O（logb）

定理

当a与b都为正整数且a>b时，记gcd(a,b)为a与b的最大公约数，则有gcd（a,b）=gcd（b, a mod b）

证明

a可以表示成 a = kb + r（a，b，k，r皆为正整数，且r不为0）

假设d是a，b的一个公约数，则有d|a，d|b，即a和b都可以被d整除。（x|y意为kx = y，k为正整数）

而r = a - kb，两边同时除以d，r/d = a/d - kb/d，由等式右边可知m = r/d为整数，因此d|r

因此d也是b，a mod b的公约数

故（a,b）与（b, a mod b）的公约数相等，则其最大公约数也相等，得证。

举例

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 / 615 = 3 （余 152）
615 / 152 = 4（余7）
152 / 7 = 21（余5）
7 / 5 = 1 （余2）
5 / 2 = 2 （余1）
2 / 1 = 2 （余0）
至此，最大公约数为1。

1.递归版

1
2
3
4
5
int gcd(int a,int b)
{
	if(b==0)return a;
	else return gcd(b,a%b);
}

2.循环版

1
2
3
4
5
6
7
8
9
10
11
12
int gcd(int a,int b)
{
    int c;
    while(a % b != 0)
    {
       c = a % b;
       a = b;
       b = c;
    }
    return b;

}

3.内置函数

C++可以使用内置函数__gcd（a,b）来求两数的最大公约数，使用时需包含头文件algorithm。

4.求最大公倍数

1
2
3
4
int lcm(int a,int b)
{
	return a/gcd(a,b)*b;
}

扩展欧几里得算法

给定两个整数a和b，求一组整数解（x,y)使得ax+by=gcd(a,b)成立，其中gcd(a,b)表示a和b的最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int g=exgcd(b,a%b,x,y);//递归计算exgcd(b,a%b)
    int temp=x;//存放x的值
    x=y;//更新x=y(old)
    y=temp-a/b*y;  //更新y=x(old)-a/b*y(old)
    return g;  //g是gcd
    
}

求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
数学问题
上一篇:
图论

    • Copyright © 2022 hnuyl16 | Powered by Hexo | Theme Bamboo