高精度加法
当数据的值特别大, 各种类型都存不下的时候,
此时就要用高精度算法来计算加减乘除:
- 先用字符串读入这个数, 然后用数组逆序存储该数的每一位
- 利用数组, 模拟加减乘除运算过程
高精度算法本质上还是模拟算法,
用代码模拟小学列竖式计算加减乘除的过程.
https://www.luogu.com.cn/problem/P1601
参考模板
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;
string x, y;
int la, lb, lc;
int a[N], b[N], c[N];
void add()
{
for (int i = 0; i < lc; i++)
{
c[i] += a[i] + b[i];
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
if (c[lc])
lc++;
}
int main()
{
cin >> x >> y;
la = x.size(), lb = y.size(), lc = max(la, lb);
for (int i = 0; i < la; i++)
a[la - 1 - i] = x[i] - '0';
for (int i = 0; i < lb; i++)
b[lb - 1 - i] = y[i] - '0';
add();
for (int i = lc - 1; i >= 0; i--)
{
cout << c[i];
}
return 0;
}
|
高精度减法
https://www.luogu.com.cn/problem/P2142
参考模板
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
| #include <iostream>
#include <string>
using namespace std;
const int N = 1e6;
string x, y;
int la, lb, lc;
int a[N], b[N], c[N];
bool isSmall(string x, string y)
{
if (x.size() != y.size())
return x.size() < y.size();
else
return x < y;
}
void sub()
{
for (int i = 0; i < lc; i++)
{
c[i] += a[i] - b[i];
if (c[i] < 0)
{
c[i + 1] -= 1;
c[i] += 10;
}
}
while (c[lc - 1] == 0 && lc - 1 > 0)
lc--;
}
int main()
{
cin >> x >> y;
if (isSmall(x, y))
{
swap(x, y);
cout << '-';
}
la = x.size(), lb = y.size(), lc = max(la, lb);
for (int i = 0; i < la; i++)
a[la - 1 - i] = x[i] - '0';
for (int i = 0; i < lb; i++)
b[lb - 1 - i] = y[i] - '0';
sub();
for (int i = lc - 1; i >= 0; i--)
{
cout << c[i];
}
return 0;
}
|
高精度乘法
https://www.luogu.com.cn/problem/P1303
参考模板
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
| #include <iostream>
#include <string>
using namespace std;
const int N = 1e5;
string x, y;
int la, lb, lc;
int a[N], b[N], c[N];
void multi()
{
for (int i = 0; i < la; i++)
{
for (int j = 0; j < lb; j++)
{
c[i + j] += a[i] * b[j];
}
}
for (int i = 0; i < lc; i++)
{
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
while (c[lc - 1] == 0 && lc - 1 > 0)
{
lc--;
}
}
int main()
{
cin >> x >> y;
la = x.size(), lb = y.size(), lc = la + lb;
for (int i = 0; i < la; i++)
a[la - 1 - i] = x[i] - '0';
for (int i = 0; i < lb; i++)
b[lb - 1 - i] = y[i] - '0';
multi();
for (int i = lc - 1; i >= 0; i--)
{
cout << c[i];
}
return 0;
}
|
高精度除法
https://www.luogu.com.cn/problem/P1480
参考模板
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
| #include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll t = 0;
string x;
int b, la, lc;
const int N = 1e5;
int a[N], c[N];
void div()
{
for (int i = la - 1; i >= 0; i--)
{
t = t * 10 + a[i];
c[i] = t / b;
t %= b;
}
while (c[lc - 1] == 0 && lc - 1 > 0)
{
lc--;
}
}
int main()
{
cin >> x >> b;
la = x.size(), lc = la;
for (int i = 0; i < la; i++)
a[la - 1 - i] = x[i] - '0';
div();
for (int i = lc - 1; i >= 0; i--)
{
cout << c[i];
}
return 0;
}
|
