- C++
高精度除以高精度模板
- 2023-12-9 17:57:03 @
#include<bits/stdc++.h>
using namespace std;
//比较函数,比较两个可变数组A和B的大小
bool cmp(vector<int> &A, vector<int> &B){
//如果两个可变数组长度不相等,返回A的长度是否大于B的长度
if(A.size()!=B.size()) return A.size()>B.size();
//从后往前遍历,比较A和B的每一个元素
for(int i=A.size()-1;i>=0;i--){
//如果A和B的元素不相等,返回A的元素是否大于B的元素
if(A[i]!=B[i]) return A[i]>B[i];
}
//如果A和B完全相等,返回true
return true;
}
//求两个可变数组A和B的差值
vector<int> sub(vector<int> &A,vector<int> &B){
//定义一个可变数组C,用来存储A和B的差值
vector<int> C;
//定义一个变量t,用来存储A和B的差值
int t=0;
//从前往后遍历,计算A和B的差值
for(int i=0;i<A.size()||t;i++){
//计算A和B的差值
t = A[i] - t;
//如果B的长度大于A的长度,则减去B的元素
if(i<B.size()) t -= B[i];
//将A和B的差值放入C中
C.push_back((t+10)%10);
//如果A和B的差值为负数,则将t置为1
if(t<0) t = 1;
//否则将t置为0
else t = 0;
}
//如果C的最后一个元素为0,则将其弹出
while(C.size()>1&&C.back()==0) C.pop_back();
//返回C
return C;
}
//求两个可变数组A和B的商和余数
vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r){
//定义一个可变数组C,用来存储商
vector<int> C;
//如果A和B不相等,则商为0,余数为A
if(!cmp(A,B)){
C.push_back(0);
r.assign(A.begin(),A.end());
return C;
}
//定义一个变量j,用来记录B的长度
int j = B.size();
//将A剩余的元素赋值给r
r.assign(A.end()-j,A.end());
//当j小于A的长度时,循环计算商和余数
while(j<=A.size()){
//定义一个变量k,用来记录商
int k=0;
//当r和B不相等时,循环计算商
while(cmp(r,B)){
//计算r和B的差值
vector<int> s = sub(r,B);
//将r的差值赋值给r
r.clear();
r.assign(s.begin(),s.end());
//k自增
k++;
}
//将商放入C中
C.push_back(k);
//如果j小于A的长度,则将A剩余的元素放入r中
if(j<A.size()) r.insert(r.begin(),A[A.size()-j-1]);
//如果r的长度大于1,且r的最后一个元素为0,则将其弹出
if(r.size()>1&&r.back()==0) r.pop_back();
//j自增
j++;
}
//将C反转
reverse(C.begin(),C.end());
//如果C的最后一个元素为0,则将其弹出
while(C.size()>1&&C.back()==0) C.pop_back();
//返回C
return C;
}
int main(){
//定义两个字符串a和b
string a,b;
//从标准输入中读取a和b
cin>>a>>b;
//定义两个可变数组A、B和r
vector<int> A,B,r;
//将a的每一个元素转换为数字,放入A中
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
//将b的每一个元素转换为数字,放入B中
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
//调用div函数,计算商和余数
auto C = div(A,B,r);
//将商放入标准输出中
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
printf("\n");
//将余数放入标准输出中
for(int i=r.size()-1;i>=0;i--) printf("%d",r[i]);
return 0;
}
0 条评论
目前还没有评论...