数学问题
发表于: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的最后一位1lowbit(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;
}
上一篇:
图论