加法 \(add\)

string add(string s1,string s2) {    //时间复杂度 O(log n)
    string res="";
    int carry=0,i=0;
    while(i<int(s1.size())||i<int(s2.size())||carry>0) {
        int a=(i<int(s1.size()))?(s1[int(s1.size())-i-1]-'0'):0;
        int b=(i<int(s2.size()))?(s2[int(s2.size())-i-1]-'0'):0;
        res+=((a+b+carry)%10)+'0';
        carry=(a+b+carry)/10;
        i++;
    }
    reverse(res.begin(),res.end());
    return res;
}

减法 \(sub\)

string sub(string a, string b) {	//时间复杂度 O(log n)
	string res;
	int c=0;
    if(a.size()<b.size()) a=string(b.size()-a.size(),'0')+a;
    else if(a.size()>b.size()) b=string(a.size()-b.size(),'0')+b;
    for(int i=a.size()-1;i>=0;i--) {
        int d=a[i]-b[i]-c;
        if(d<0) d+=10,c=1;
        else c=0;
        res.push_back(d+'0');
    }
    reverse(res.begin(),res.end());
    while(res.size()>1&&res[0]=='0') {
        res.erase(res.begin());
    }
    return res;
}

乘法 \(mul\)

string mul(string num1,string num2) {	//时间复杂度 O(n^2)
    string res(int(num1.length())+int(num2.length()),'0');
    for(int i=int(num1.length())-1;i>=0;i--) {
        for(int j=int(num2.length())-1;j>=0;j--) {
            int pd=(num1[i]-'0')*(num2[j]-'0');
            int p1=i+j;
            int p2=i+j+1;
            int sum=pd+(res[p2]-'0');
            res[p2]=sum%10+'0';
            res[p1]+=sum/10;
        }
    }
    int i=0;
    while(i<int(res.length())&&res[i]=='0') {
        i++;
    }
    return i==int(res.length())?"0":res.substr(i);
}

#include <iostream>
#include <vector>
using namespace std;
// 将字符串转换为整数数组
vector<int> strToVec(string str) {
	vector<int> vec;
	for (int i = str.length() - 1; i >= 0; i--) {
		vec.push_back(str[i] - '0');
	}
	return vec;
}
// 将整数数组转换为字符串
string vecToStr(vector<int> vec) {
	string str = "";
	for (int i = vec.size() - 1; i >= 0; i--) {
		str += to_string(vec[i]);
	}
	return str;
}
// 高精度加法
vector<int> add(vector<int> num1, vector<int> num2) {
	vector<int> result;
	int carry = 0;
	int len1 = num1.size();
	int len2 = num2.size();
	int maxLen = max(len1, len2);
	for (int i = 0; i < maxLen; i++) {
		int digit1 = i < len1 ? num1[i] : 0;
		int digit2 = i < len2 ? num2[i] : 0;
		int sum = digit1 + digit2 + carry;
		result.push_back(sum % 10);
		carry = sum / 10;
	}
	if (carry != 0) {
		result.push_back(carry);
	}
	return result;
}
// 高精度乘法
vector<int> mul(vector<int> num1, vector<int> num2) {
	int len1 = num1.size();
	int len2 = num2.size();
	// 递归终止条件
	if (len1 == 0 || len2 == 0) {
		return vector<int>();
	}
	// 递归基
	if (len1 == 1 && len2 == 1) {
		vector<int> result;
		int product = num1[0] * num2[0];
		result.push_back(product % 10);
		if (product >= 10) {
			result.push_back(product / 10);
		}
		return result;
	}
	// 将数字分为两部分
	int mid = min(len1, len2) / 2;
	vector<int> num1Low(num1.begin(), num1.begin() + mid);
	vector<int> num1High(num1.begin() + mid, num1.end());
	vector<int> num2Low(num2.begin(), num2.begin() + mid);
	vector<int> num2High(num2.begin() + mid, num2.end());
	// 递归计算
	vector<int> z0 = mul(num1Low, num2Low);
	vector<int> z1 = mul(num1High, num2High);
	vector<int> z2 = mul(add(num1Low, num1High), add(num2Low, num2High));
	z2 = add(z2, z0);
	z2 = add(z2, z1);
	// 合并结果
	vector<int> result;
	result.insert(result.end(), z0.begin(), z0.end());
	result.insert(result.begin() + mid, z2.begin(), z2.end());
	result.insert(result.begin() + 2 * mid, z1.begin(), z1.end());
	return result;
}
int main() {
	string str1, str2;
	cout << "请输入两个整数：" << endl;
	cin >> str1 >> str2;
	vector<int> num1 = strToVec(str1);
	vector<int> num2 = strToVec(str2);
	vector<int> result = mul(num1, num2);
	string strResult = vecToStr(result);
	cout << "两个整数的乘积为：" << endl;
	cout << strResult << endl;
	return 0;
}

除法&取余 \(divi\)

两个正数相除，商为\(quotient\),余数为\(residue\)

int compare(string str1,string str2) {
    if(str1.length()>str2.length()) return 1;
    else if(str1.length()<str2.length())  return -1;
    else return str1.compare(str2);
}
string sub(string a, string b) {	//时间复杂度 O(log n)
	string res;
	int c=0;
    if(a.size()<b.size()) a=string(b.size()-a.size(),'0')+a;
    else if(a.size()>b.size()) b=string(a.size()-b.size(),'0')+b;
    for(int i=a.size()-1;i>=0;i--) {
        int d=a[i]-b[i]-c;
        if(d<0) d+=10,c=1;
        else c=0;
        res.push_back(d+'0');
    }
    reverse(res.begin(),res.end());
    while(res.size()>1&&res[0]=='0') {
        res.erase(res.begin());
    }
    return res;
}
string mul(string num1,string num2) {   //时间复杂度 O(n^2)
    string res(int(num1.length())+int(num2.length()),'0');
    for(int i=int(num1.length())-1;i>=0;i--) {
        for(int j=int(num2.length())-1;j>=0;j--) {
            int pd=(num1[i]-'0')*(num2[j]-'0');
            int p1=i+j;
            int p2=i+j+1;
            int sum=pd+(res[p2]-'0');
            res[p2]=sum%10+'0';
            res[p1]+=sum/10;
        }
    }
    int i=0;
    while(i<int(res.length())&&res[i]=='0') {
        i++;
    }
    return i==int(res.length())?"0":res.substr(i);
}
void divi(string str1,string str2,string &quotient,string &residue) {
	quotient=residue="";
	if(str2=="0") {
		quotient=residue="ERROR";
		return;
	}
	if(str1=="0") {
		quotient=residue="0";
		return;
	}
	int res=compare(str1,str2);
	if(res<0) {
		quotient="0";
		residue=str1;
		return;
	} else if(res==0) {
		quotient="1";
		residue="0";
		return;
	} else {
		int len1=str1.length();
		int len2=str2.length();
		string tempstr;
		tempstr.append(str1,0,len2-1);
		for (int i=len2-1;i<len1;i++) {
			tempstr=tempstr+str1[i];
			tempstr.erase(0,tempstr.find_first_not_of('0'));
			if(tempstr.empty()) tempstr="0";
			for (char ch='9';ch>='0';ch--) {
				string str,tmp;
				str=str+ch;
				tmp=mul(str2,str);
				if(compare(tmp,tempstr)<=0) {
					quotient=quotient+ch;
					tempstr=sub(tempstr,tmp);
					break;
				}
			}
		}
		residue=tempstr;
	}
	quotient.erase(0,quotient.find_first_not_of('0'));
	if(quotient.empty()) quotient="0";
}

本栏目推荐文章
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【解决方案】Error running,Command line is too long
• Spark读写达梦数据库报错Decimal精度为负数以及解决方案
• c++编译OpenSceneGraph-3.4 出现 error: narrowing conversion of ‘-1’ from ‘int’ to ‘char’ inside { } [-Wnarrowing]
• C语言中这几种数组，弄明白了吗？int(*pai[2])[5]，int *aapi[2][2]， int **p[2]， int *numT[5]， int(*num2)[5]
• （坚持每天写算法）算法复习与学习part1基础算法1-6——高精度加法
• C语言int * (* (*fp1) (int) ) [10]声明是啥意思呢？
• java_Long、long精度丢失问题
• C/C++函数参数声明解析：int fun() 与 int fun(void) 的差异揭秘
• QT6.4.3中，关于QString asprintf(const char*cformat,...)与int asprintf(char**strp,const char*fmt,...)的使用问题

高精 long 高精度 int高精long高精度int demo6 demo long int 数组long元素int long int p1401 18 高精度 高精 运算符java long int 高精 高精度 高精 高精度 算法 高精 加法 高精度