A41110. 大整数除法
填空题
较难
知识点
题目描述
大整数除法
题目描述
求两个大的正整数相除的商。
输入格式
第1行是被除数，第2行是除数。每个数均不超过100位。
输出格式
一行，相应的商的整数部分。
样例输入
2376
24
样例输出
99
参考答案
#include <iostream>
#include <cstring>
using namespace std;
char a[110],b[110];
int aa[110],bb[110];
int main(){
cin>>a;//输入字符串与转换为常数数组
cin>>b;
int len_a=strlen(a);
int len_b=strlen(b);
if(len_a<len_b){
cout<<0;
return 0;
}
for (int i = 0; i < len_a; ++i) {
aa[i]=a[i]-'0';
}
for (int i = 0; i < len_b; ++i) {
bb[i]=b[i]-'0';
}
int k=0,ff=0;//k为首位置，ff为标记是否为初始为零情况
for (int i = len_b; i <= len_a; ++i) {//i为尾位置
int num=0;
while(true){
int flag=1;//用于标记位数相同时情况
int temp=0;
int all=0;
if(aa[k]==0)k++;
if(i-k<len_b)break;
else if (i-k==len_b){//位数相同时
for (int l = k; l < i; ++l) {
if(aa[l]>bb[temp]){
flag=0;
int tt=0;
for (int j = k; j < l; ++j) {
if(aa[j]<bb[tt++])flag=1;
}
break;
}
if(aa[l]==bb[temp]){
all++;
}
temp++;
}//比较
if(all==len_b)flag=0;
if(flag)break;
}
ff=1;
int bbb=len_b-1;
for (int j = i-1; j >= k ; j--) {//减
if(aa[j]<bb[bbb]){
aa[j]+=10;
aa[j-1]-=1;
aa[j]-=bb[bbb];
}else{
aa[j]-=bb[bbb];
}
bbb--;
}
num++;
}
if(ff||len_a==len_b)cout<<num;
}
}
上一题
下一题