加法 \(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 "ient,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";
}