一维前缀和
1 | //现有数组 |
程序示例
1 |
|
二维前缀和
- 使用
s[i,j]来代表a[i,j]左上方的所有元素的和，那么它可以表示为s[i,j]=s[i,j-1]+s[i-1,j]-s[i-1,j-1]+a[i,j]
代码展示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//二维前缀和
using namespace std;
int main(){
int a[N][M];
int i,j;
int s[N][M];
//输入数组
for(i=1;i<=3;i++){
for(j=1;j<=4;j++){
cin>>a[i][j];
}
}
//求二维前缀和
for(i=1;i<=3;i++){
for(j=1;j<=4;j++){
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
cout<<s[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
求最大公约数及最小公倍数
辗转相除法
1
2
3
4
5
6
7
8
9
10
11int zhanzhuanchugcd(int a, int b)
{
if(a%b==0){
return b;
}
else{
return zhanzhuangcd(b,a%b);
}
}
//保证a>b
//判断a%b=0辗转相减法
1
2
3
4
5
6
7
8
9
10
11
12
13int zhanzhuanjiangcd(int a,int b)
{
while(a!=b){
if(a>b){
a=a-b;
}
else{
b=b-a;
}
}
return b;
}
//判断 a==b穷举法
1
2
3
4
5
6
7
8
9
10int qiongju(int a,int b)
{
int temp =0;
temp = a>b?b:a;
for(;;temp--){
if(a%temp==0&&b%temp==0)
break;
}
return temp;
}最小公倍数 =
a*b/gcd(a,b)