- 李奕樊's blog
[团队]重写高精度&&不一样的高精度&&高精度教程
-
李奕樊
LV 9
@
2024-7-20 8:48:37
前言
个人不太喜欢数组式高精度的代码， 所以重写了。
思路：结构体 + 运算符重载
讲解
大整数加法
目标详解
对于高精度加法a + b = ans，参照加法的竖式运算，加法运算符重载时，主要任务就是结果ans的两个成员变量a[]和len的赋值。
对于len的赋值，加法运算结果的位数至少是参与运算的a.len和b.len的较大值，若是发生了最高位进位，比如999 + 1 = 1000，则再多一位。
而对于a[]的赋值，基本思路如下：
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i] + b.a[i];
当然，还得考虑进位的问题，由于a[]的存储是从低位到高位存的，所以进位到+1位即可：
for(int i = 1; i <= ans.len; i++){
ans.a[i] = a.a[i] + b.a[i];
ans.a[i + 1] = ans.a[i] / 10;
ans.a[i] %= 10;
}
但是这样写的话，进位的数据并没有加到结果中，所以：
for(int i = 1; i <= ans.len; i++){
ans.a[i] += a.a[i] + b.a[i]; // 此处改为 +=
ans.a[i + 1] = ans.a[i] / 10;
ans.a[i] %= 10;
}
最后再考虑最高位的进位情况：
if(ans.a[ ans.len + 1 ])
ans.len++;
代码
#include<iostream>
using namespace std;
const int N = 1005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位，个位数在前
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
// 运算符重载也可以写在结构体内部
// BigInt operator + (const BigInt& b) const{...}
};
// 运算符重载 加法
BigInt operator + (const BigInt& a, const BigInt& b){
BigInt ans;
ans.len = max(a.len, b.len); // 至少
for(int i = 1; i <= ans.len; i++){
ans.a[i] += a.a[i] + b.a[i];
ans.a[i + 1] = ans.a[i] / 10;
ans.a[i] %= 10;
}
if(ans.a[ ans.len + 1 ])
ans.len++;
return ans;
}
int main(){
string s1, s2;
cin >> s1 >> s2;
BigInt a(s1), b(s2);
BigInt c = a + b;
c.show();
return 0;
}
大整数减法
目标详解
对于减法运算，会涉及到大小和正负问题，为了方便，我们可以提前判断大小关系，始终保证大减小。
- 高精度大小比较 对于两个高精度数a和b，判断二者大小关系：
首先应当先看位数，位数大的肯定大。 若位数相同，则从高位往低位逐个比较，第一次发现不同时即可判断出大小关系。 若始终都相同，则两数相等 2. 高精度减法 对于高精度减法a - b = ans，参照减法的竖式运算，减法运算符重载时，主要任务就是结果ans的两个成员变量a[]和len的赋值。
对于len的赋值，减法运算中结果的位数至多为参与运算的a.len和b.len的较大值，可能会减少较多，比如1000 - 999 = 1。
而对于a[]的赋值，基本思路如下：
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i] - b.a[i];
考虑借位的问题，由于a-b得到ans不能改动a和b的值，所以借位要发生在ans上（也可以减法之前将a赋值到ans上）：
for(int i = 1; i <= ans.len; i++){
if(a.a[i] < b.a[i]){
ans.a[i] += 10;
ans.a[i + 1]--;
}
ans.a[i] += a.a[i] - b.a[i]; // 改为+=
}
但仍有特殊情况，考虑190-99的十位的减法，最终写法：
for(int i = 1; i <= ans.len; i++){
if(ans.a[i] + a.a[i] < b.a[i]){
ans.a[i] += 10;
ans.a[i + 1]--;
}
ans.a[i] += a.a[i] - b.a[i];
}
最后，考虑位数的变化：
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
注意：由于a[0]值为0，要小心ans.len减为负数，发生在相等的两数相减时。
代码
#include<iostream>
using namespace std;
const int N = 1005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
};
// 运算符重载 大于等于
bool operator >= (const BigInt& a, const BigInt& b){
if(a.len != b.len)
return a.len > b.len;
for(int i = a.len; i >= 1; i--)
if(a.a[i] != b.a[i])
return a.a[i] > b.a[i];
return true; // a b 相等
}
// 运算符重载 减法 大减小
BigInt operator - (const BigInt& a, const BigInt& b){
BigInt ans;
ans.len = max(a.len, b.len); // 至多
for(int i = 1; i <= ans.len; i++){
if(ans.a[i] + a.a[i] < b.a[i]){
ans.a[i] += 10;
ans.a[i + 1]--;
}
ans.a[i] += a.a[i] - b.a[i];
}
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
return ans;
}
int main(){
string s1, s2;
cin >> s1 >> s2;
BigInt a(s1), b(s2);
BigInt c;
if(a >= b)
c = a - b;
else{
c = b - a;
cout << '-';
}
c.show();
return 0;
}
大整数乘法
目标详解
对于高精度乘法a * b = ans，参照乘法的竖式运算，乘法运算符重载时，主要任务就是结果ans的两个成员变量a[]和len的赋值。
对于len的赋值，乘法运算中结果的位数至少为a.len + b.len - 1，若发生最高位进位则再多一位。
而对于a[]的赋值，由于a*b实际为a的每一位乘以了b的每一位，再分别算入结果的对应为中，所以基本思路：
for(int i = 1; i <= a.len; i++)
for(int j = 1; j <= b.len; j++)
ans.a[?] = a.a[i] * b.a[j];
至于对应哪一位，需要自行总结感受，应为i + j - 1。此外再考虑进位，由于乘法中ans的下标在不停变化，因此应注意ans.a[x]本来就有值的情况：
for(int i = 1; i <= a.len; i++)
for(int j = 1; j <= b.len; j++){
int k = i + j - 1;
ans.a[k] += a.a[i] * b.a[j]; // 注意+=
ans.a[k + 1] += ans.a[k] / 10; // 注意+=
ans.a[k] %= 10;
}
最后再考虑最高位的进位情况：
if(ans.a[ ans.len + 1 ])
ans.len++;
代码
#include<iostream>
using namespace std;
const int N = 2005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
};
// 运算符重载 乘法
BigInt operator * (const BigInt& a, const BigInt& b){
BigInt ans;
ans.len = a.len + b.len - 1; // 至少
for(int i = 1; i <= a.len; i++)
for(int j = 1; j <= b.len; j++){
int k = i + j - 1;
ans.a[k] += a.a[i] * b.a[j];
ans.a[k + 1] += ans.a[k] / 10;
ans.a[k] %= 10;
}
if(ans.a[ ans.len + 1 ])
ans.len++;
return ans;
}
int main(){
string s1, s2;
cin >> s1 >> s2;
BigInt a(s1), b(s2);
BigInt c = a * b;
c.show();
return 0;
}
大整数截取
目标详解
在实际高精度题目中，由于数据量较大，常常要求截取高精度数据的末几位。
由于截取本质上相当于模10的幂（截取3位就是模1000），所以常通过重载模运算符来实现。
若要截取某个高精度数据的后1000位，则需要对10^1000取余，数据量太大。
所以高精度截取中，高精度数a % 1000的含义就是截取后3位，并不是对1000求余。（废话）
对于高精度数据截取a % p = ans，确定ans的a[]和len即可。
对于位数长度len，至多为p位，考虑1001截取后三位。
而对于a[]，复制即可：
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i];
然后考虑位数变化：
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
注意： a[0]的值为0，要避免ans.len减为负数的情况，比如1000取末3位。
代码
#include<iostream>
using namespace std;
const int N = 1005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
};
// 运算符重载 模 并非取模，实际为截取后p位
BigInt operator % (const BigInt& a, int p){
BigInt ans;
ans.len = p;
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i];
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
return ans;
}
int main(){
string s;
int p;
cin >> s >> p;
BigInt a(s);
a = a % p;
a.show();
return 0;
}
大整数除法
目标详解
1、思路 首先将大数存储为数组。然后有多种方法可以采用：
朴素算法：循环减（模拟除），一直到余数小于除数 连减法：每次按位截取用来滚动减，记录到结果数组里 2、连减法 方便起见我们以两个数 3450除以17模拟： 3450有4位，17有2位，于是从4-2+1 = 3开始（即3450的4位置为第一次个位数）
步骤1：取出3450的前2位34，开始连减得到d[3] = 34/17=2，r=0
步骤2：取出下一位5，累加到r（5），得到d[2] = 5/17=0，r=0，
步骤3：取下一位0累加到r（50）,得到d[1] = 50/17 = 2，r=16
最后结果，商为202，余数为16
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2005;
struct BigInt {
int a[N], len;
void init() {
for(int i=1; i<=N-1; i++)
a[i] = 0;
len = 0;
}
BigInt(){
init();
}
BigInt(string s) {
init();
len = s.length();
for(int i=1; i<=len; i++)
a[i] = s[len-i] - '0';
}
void show() {
if(len == 0) {
printf("0");
return;
}
for(int i=len; i>=1; i--)
printf("%d", a[i]);
}
bool less(const BigInt &b1) const {
if(len == b1.len) {
for(int i=len; i>=1; i--) {
if(a[i] == b1.a[i]) continue;
return a[i] < b1.a[i];
}
return false;
} else
return len < b1.len;
}
bool operator < (const BigInt &b1) const {
return less(b1);
}
//位除，结果为商，自己变为余数
int dd(const BigInt &n2) {
int k = 0;//商
while(!(less(n2))) {//*this >= n2
for(int i=1; i<=len; i++) {
if(a[i] < n2.a[i]) {//借位
a[i] += 10;
a[i+1]--;
}
a[i] -= n2.a[i];
}
for(int i=len; i>=1 && a[i]==0; i--) //高位去0
len--;
k++;
}
return k;
}
//按位除下去，由于控制了除的起始位，每次的商不会超过10，可以存储到ans里
BigInt devide(const BigInt &n2, BigInt &r) const {
BigInt ans;
if(less(n2)) {
r.len = len;
for(int i=1; i<=len; i++)
r.a[i] = a[i];
return ans;//n1 < n2
}
ans.len = len - n2.len + 1;//可除的最高位
r.len = n2.len;
for(int i=1; i<=r.len; i++)
r.a[i] = a[ans.len-1+i];
ans.a[ans.len] = r.dd(n2);
for(int i = ans.len-1; i>=1; i--) {
for(int j=r.len+1; j>=2; j--)
r.a[j] = r.a[j-1];
r.a[1] = a[i];
r.len++;
ans.a[i] = r.dd(n2);
}
if(ans.a[ans.len] == 0) ans.len--;
return ans;
}
};
int main() {
string s1, s2;
cin>>s1>>s2;
BigInt b1(s1), b2(s2), r;
BigInt b3 = b1.devide(b2, r);
b3.show();
cout<<endl;
r.show();
cout<<endl;
return 0;
}
大整数的幂
目标详解
对于高精度幂运算a^b，其中a为高精度数据，b为普通数。
一般而言，由于结果十分大，所以题目常会要求得到末几位即可，而幂运算算完后取末几位与每乘一次就取一次的结果是一样的。
因此，只要借助循环，让b个a相乘，每次乘完后就立马取出末几位作为下一次乘的因子即可。
也就是说，只要实现高精度数的乘法和截取，再控制好幂运算流程，便能得出正确的结果：
BigInt operator * (const BigInt& a, const BigInt& b){...}
BigInt operator % (const BigInt& a, const int& b){...}
但实际上，高精度数据的幂运算依旧可以借助快速幂算法来优化，只要注意随时截取末位就好了：
BigInt quick_pow(BigInt n1, int b){
BigInt ans("1");
BigInt x = ans * n1;
while(b) {
if(b%2 == 1)
ans = (ans*x) % P;
x = (x*x) % P;
b /= 2;
}
return ans;
}
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2005, P=1000;
struct BigInt {
int a[N], len;
void init() {
for(int i=1; i<=N-1; i++)
a[i] = 0;
len = 0;
}
BigInt(){
init();
}
BigInt(string s) {
init();
len = s.length();
for(int i=1; i<=len; i++)
a[i] = s[len-i] - '0';
}
void show() {
if(len <= 0) {
printf("0");
return;
}
for(int i=len; i>=1; i--)
printf("%d", a[i]);
}
BigInt operator * (const BigInt &b1) const {
BigInt ans;
ans.len = len + b1.len - 1;
for(int i=1; i<=len; i++)
for(int j=1; j<=b1.len; j++) {
int k = i+j-1;
ans.a[k] += a[i] * b1.a[j];
ans.a[k+1] += ans.a[k] / 10;
ans.a[k] = ans.a[k] % 10;
}
if(ans.a[ans.len+1]) ans.len++;
return ans;
}
//p位取余
BigInt operator % (const int p) const {
BigInt ans;
ans.len = min(len, p);
for(int i=1; i<=ans.len; i++)
ans.a[i] = a[i];
for(int i=ans.len; i>=1; i--) {
if(ans.a[i] == 0)
ans.len--;
else
break;
}
return ans;
}
};
BigInt quick_pow(BigInt n1, ll b) {
BigInt ans("1");
BigInt x = ans * n1;
while(b) {
if(b%2 == 1)
ans = (ans*x) % P;
x = (x*x) % P;
b /= 2;
}
return ans;
}
int main() {
string s1;
ll b;
cin>>s1>>b;
BigInt n1(s1);
BigInt b3 = quick_pow(n1, b);
b3.show();
cout<<endl;
return 0;
后言
因为编辑器不是DEV,导致缩进是2格,自己也懒得加空格了,看看吧. 压位优化懒得写, 以后写吧, 改为short应该有优化 作者制作不易,转载请标注作者## 前言 个人不太喜欢数组式高精度的代码， 所以重写了。 blog 思路：结构体 + 运算符重载
讲解
大整数加法
目标详解
对于高精度加法a + b = ans，参照加法的竖式运算，加法运算符重载时，主要任务就是结果ans的两个成员变量a[]和len的赋值。
对于len的赋值，加法运算结果的位数至少是参与运算的a.len和b.len的较大值，若是发生了最高位进位，比如999 + 1 = 1000，则再多一位。
而对于a[]的赋值，基本思路如下：
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i] + b.a[i];
当然，还得考虑进位的问题，由于a[]的存储是从低位到高位存的，所以进位到+1位即可：
for(int i = 1; i <= ans.len; i++){
ans.a[i] = a.a[i] + b.a[i];
ans.a[i + 1] = ans.a[i] / 10;
ans.a[i] %= 10;
}
但是这样写的话，进位的数据并没有加到结果中，所以：
for(int i = 1; i <= ans.len; i++){
ans.a[i] += a.a[i] + b.a[i]; // 此处改为 +=
ans.a[i + 1] = ans.a[i] / 10;
ans.a[i] %= 10;
}
最后再考虑最高位的进位情况：
if(ans.a[ ans.len + 1 ])
ans.len++;
代码
#include<iostream>
using namespace std;
const int N = 1005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位，个位数在前
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
// 运算符重载也可以写在结构体内部
// BigInt operator + (const BigInt& b) const{...}
};
// 运算符重载 加法
BigInt operator + (const BigInt& a, const BigInt& b){
BigInt ans;
ans.len = max(a.len, b.len); // 至少
for(int i = 1; i <= ans.len; i++){
ans.a[i] += a.a[i] + b.a[i];
ans.a[i + 1] = ans.a[i] / 10;
ans.a[i] %= 10;
}
if(ans.a[ ans.len + 1 ])
ans.len++;
return ans;
}
int main(){
string s1, s2;
cin >> s1 >> s2;
BigInt a(s1), b(s2);
BigInt c = a + b;
c.show();
return 0;
}
大整数减法
目标详解
对于减法运算，会涉及到大小和正负问题，为了方便，我们可以提前判断大小关系，始终保证大减小。
- 高精度大小比较 对于两个高精度数a和b，判断二者大小关系：
首先应当先看位数，位数大的肯定大。 若位数相同，则从高位往低位逐个比较，第一次发现不同时即可判断出大小关系。 若始终都相同，则两数相等 2. 高精度减法 对于高精度减法a - b = ans，参照减法的竖式运算，减法运算符重载时，主要任务就是结果ans的两个成员变量a[]和len的赋值。
对于len的赋值，减法运算中结果的位数至多为参与运算的a.len和b.len的较大值，可能会减少较多，比如1000 - 999 = 1。
而对于a[]的赋值，基本思路如下：
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i] - b.a[i];
考虑借位的问题，由于a-b得到ans不能改动a和b的值，所以借位要发生在ans上（也可以减法之前将a赋值到ans上）：
for(int i = 1; i <= ans.len; i++){
if(a.a[i] < b.a[i]){
ans.a[i] += 10;
ans.a[i + 1]--;
}
ans.a[i] += a.a[i] - b.a[i]; // 改为+=
}
但仍有特殊情况，考虑190-99的十位的减法，最终写法：
for(int i = 1; i <= ans.len; i++){
if(ans.a[i] + a.a[i] < b.a[i]){
ans.a[i] += 10;
ans.a[i + 1]--;
}
ans.a[i] += a.a[i] - b.a[i];
}
最后，考虑位数的变化：
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
注意：由于a[0]值为0，要小心ans.len减为负数，发生在相等的两数相减时。
代码
#include<iostream>
using namespace std;
const int N = 1005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
};
// 运算符重载 大于等于
bool operator >= (const BigInt& a, const BigInt& b){
if(a.len != b.len)
return a.len > b.len;
for(int i = a.len; i >= 1; i--)
if(a.a[i] != b.a[i])
return a.a[i] > b.a[i];
return true; // a b 相等
}
// 运算符重载 减法 大减小
BigInt operator - (const BigInt& a, const BigInt& b){
BigInt ans;
ans.len = max(a.len, b.len); // 至多
for(int i = 1; i <= ans.len; i++){
if(ans.a[i] + a.a[i] < b.a[i]){
ans.a[i] += 10;
ans.a[i + 1]--;
}
ans.a[i] += a.a[i] - b.a[i];
}
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
return ans;
}
int main(){
string s1, s2;
cin >> s1 >> s2;
BigInt a(s1), b(s2);
BigInt c;
if(a >= b)
c = a - b;
else{
c = b - a;
cout << '-';
}
c.show();
return 0;
}
大整数乘法
目标详解
对于高精度乘法a * b = ans，参照乘法的竖式运算，乘法运算符重载时，主要任务就是结果ans的两个成员变量a[]和len的赋值。
对于len的赋值，乘法运算中结果的位数至少为a.len + b.len - 1，若发生最高位进位则再多一位。
而对于a[]的赋值，由于a*b实际为a的每一位乘以了b的每一位，再分别算入结果的对应为中，所以基本思路：
for(int i = 1; i <= a.len; i++)
for(int j = 1; j <= b.len; j++)
ans.a[?] = a.a[i] * b.a[j];
至于对应哪一位，需要自行总结感受，应为i + j - 1。此外再考虑进位，由于乘法中ans的下标在不停变化，因此应注意ans.a[x]本来就有值的情况：
for(int i = 1; i <= a.len; i++)
for(int j = 1; j <= b.len; j++){
int k = i + j - 1;
ans.a[k] += a.a[i] * b.a[j]; // 注意+=
ans.a[k + 1] += ans.a[k] / 10; // 注意+=
ans.a[k] %= 10;
}
最后再考虑最高位的进位情况：
if(ans.a[ ans.len + 1 ])
ans.len++;
代码
#include<iostream>
using namespace std;
const int N = 2005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
};
// 运算符重载 乘法
BigInt operator * (const BigInt& a, const BigInt& b){
BigInt ans;
ans.len = a.len + b.len - 1; // 至少
for(int i = 1; i <= a.len; i++)
for(int j = 1; j <= b.len; j++){
int k = i + j - 1;
ans.a[k] += a.a[i] * b.a[j];
ans.a[k + 1] += ans.a[k] / 10;
ans.a[k] %= 10;
}
if(ans.a[ ans.len + 1 ])
ans.len++;
return ans;
}
int main(){
string s1, s2;
cin >> s1 >> s2;
BigInt a(s1), b(s2);
BigInt c = a * b;
c.show();
return 0;
}
大整数截取
目标详解
在实际高精度题目中，由于数据量较大，常常要求截取高精度数据的末几位。
由于截取本质上相当于模10的幂（截取3位就是模1000），所以常通过重载模运算符来实现。
若要截取某个高精度数据的后1000位，则需要对10^1000取余，数据量太大。
所以高精度截取中，高精度数a % 1000的含义就是截取后3位，并不是对1000求余。（废话）
对于高精度数据截取a % p = ans，确定ans的a[]和len即可。
对于位数长度len，至多为p位，考虑1001截取后三位。
而对于a[]，复制即可：
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i];
然后考虑位数变化：
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
注意： a[0]的值为0，要避免ans.len减为负数的情况，比如1000取末3位。
代码
#include<iostream>
using namespace std;
const int N = 1005; // 高精度数位数上限
struct BigInt{
int a[N]; // 高精度数每一位
int len; // 高精度数位数
// 成员函数：初始化函数
void init(){
for(int i = 0; i < N; i++)
a[i] = 0;
len = 0;
}
// 构造函数： 无参
BigInt(){
init();
}
// 构造函数： 有参
BigInt(string s){
len = s.length();
for(int i = 1; i <= len; i++)
a[i] = s[len - i] - '0';
}
// 输出函数
void show(){
if(len == 0){
cout << 0 << endl;
return;
}
for(int i = len; i >= 1; i--)
cout << a[i];
cout << endl;
}
};
// 运算符重载 模 并非取模，实际为截取后p位
BigInt operator % (const BigInt& a, int p){
BigInt ans;
ans.len = p;
for(int i = 1; i <= ans.len; i++)
ans.a[i] = a.a[i];
while(!ans.a[ ans.len ] && ans.len > 0)
ans.len--;
return ans;
}
int main(){
string s;
int p;
cin >> s >> p;
BigInt a(s);
a = a % p;
a.show();
return 0;
}
大整数除法
目标详解
1、思路 首先将大数存储为数组。然后有多种方法可以采用：
朴素算法：循环减（模拟除），一直到余数小于除数 连减法：每次按位截取用来滚动减，记录到结果数组里 2、连减法 方便起见我们以两个数 3450除以17模拟： 3450有4位，17有2位，于是从4-2+1 = 3开始（即3450的4位置为第一次个位数）
步骤1：取出3450的前2位34，开始连减得到d[3] = 34/17=2，r=0
步骤2：取出下一位5，累加到r（5），得到d[2] = 5/17=0，r=0，
步骤3：取下一位0累加到r（50）,得到d[1] = 50/17 = 2，r=16
最后结果，商为202，余数为16
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2005;
struct BigInt {
int a[N], len;
void init() {
for(int i=1; i<=N-1; i++)
a[i] = 0;
len = 0;
}
BigInt(){
init();
}
BigInt(string s) {
init();
len = s.length();
for(int i=1; i<=len; i++)
a[i] = s[len-i] - '0';
}
void show() {
if(len == 0) {
printf("0");
return;
}
for(int i=len; i>=1; i--)
printf("%d", a[i]);
}
bool less(const BigInt &b1) const {
if(len == b1.len) {
for(int i=len; i>=1; i--) {
if(a[i] == b1.a[i]) continue;
return a[i] < b1.a[i];
}
return false;
} else
return len < b1.len;
}
bool operator < (const BigInt &b1) const {
return less(b1);
}
//位除，结果为商，自己变为余数
int dd(const BigInt &n2) {
int k = 0;//商
while(!(less(n2))) {//*this >= n2
for(int i=1; i<=len; i++) {
if(a[i] < n2.a[i]) {//借位
a[i] += 10;
a[i+1]--;
}
a[i] -= n2.a[i];
}
for(int i=len; i>=1 && a[i]==0; i--) //高位去0
len--;
k++;
}
return k;
}
//按位除下去，由于控制了除的起始位，每次的商不会超过10，可以存储到ans里
BigInt devide(const BigInt &n2, BigInt &r) const {
BigInt ans;
if(less(n2)) {
r.len = len;
for(int i=1; i<=len; i++)
r.a[i] = a[i];
return ans;//n1 < n2
}
ans.len = len - n2.len + 1;//可除的最高位
r.len = n2.len;
for(int i=1; i<=r.len; i++)
r.a[i] = a[ans.len-1+i];
ans.a[ans.len] = r.dd(n2);
for(int i = ans.len-1; i>=1; i--) {
for(int j=r.len+1; j>=2; j--)
r.a[j] = r.a[j-1];
r.a[1] = a[i];
r.len++;
ans.a[i] = r.dd(n2);
}
if(ans.a[ans.len] == 0) ans.len--;
return ans;
}
};
int main() {
string s1, s2;
cin>>s1>>s2;
BigInt b1(s1), b2(s2), r;
BigInt b3 = b1.devide(b2, r);
b3.show();
cout<<endl;
r.show();
cout<<endl;
return 0;
}
大整数的幂
目标详解
对于高精度幂运算a^b，其中a为高精度数据，b为普通数。
一般而言，由于结果十分大，所以题目常会要求得到末几位即可，而幂运算算完后取末几位与每乘一次就取一次的结果是一样的。
因此，只要借助循环，让b个a相乘，每次乘完后就立马取出末几位作为下一次乘的因子即可。
也就是说，只要实现高精度数的乘法和截取，再控制好幂运算流程，便能得出正确的结果：
BigInt operator * (const BigInt& a, const BigInt& b){...}
BigInt operator % (const BigInt& a, const int& b){...}
但实际上，高精度数据的幂运算依旧可以借助快速幂算法来优化，只要注意随时截取末位就好了：
BigInt quick_pow(BigInt n1, int b){
BigInt ans("1");
BigInt x = ans * n1;
while(b) {
if(b%2 == 1)
ans = (ans*x) % P;
x = (x*x) % P;
b /= 2;
}
return ans;
}
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2005, P=1000;
struct BigInt {
int a[N], len;
void init() {
for(int i=1; i<=N-1; i++)
a[i] = 0;
len = 0;
}
BigInt(){
init();
}
BigInt(string s) {
init();
len = s.length();
for(int i=1; i<=len; i++)
a[i] = s[len-i] - '0';
}
void show() {
if(len <= 0) {
printf("0");
return;
}
for(int i=len; i>=1; i--)
printf("%d", a[i]);
}
BigInt operator * (const BigInt &b1) const {
BigInt ans;
ans.len = len + b1.len - 1;
for(int i=1; i<=len; i++)
for(int j=1; j<=b1.len; j++) {
int k = i+j-1;
ans.a[k] += a[i] * b1.a[j];
ans.a[k+1] += ans.a[k] / 10;
ans.a[k] = ans.a[k] % 10;
}
if(ans.a[ans.len+1]) ans.len++;
return ans;
}
//p位取余
BigInt operator % (const int p) const {
BigInt ans;
ans.len = min(len, p);
for(int i=1; i<=ans.len; i++)
ans.a[i] = a[i];
for(int i=ans.len; i>=1; i--) {
if(ans.a[i] == 0)
ans.len--;
else
break;
}
return ans;
}
};
BigInt quick_pow(BigInt n1, ll b) {
BigInt ans("1");
BigInt x = ans * n1;
while(b) {
if(b%2 == 1)
ans = (ans*x) % P;
x = (x*x) % P;
b /= 2;
}
return ans;
}
int main() {
string s1;
ll b;
cin>>s1>>b;
BigInt n1(s1);
BigInt b3 = quick_pow(n1, b);
b3.show();
cout<<endl;
return 0;
后言
因为编辑器不是DEV,导致缩进是2格,自己也懒得加空格了,看看吧.
压位优化懒得写, 以后写吧, 改为short应该有优化
作者制作不易,转载请标注作者