这个代码(在版本 II 也) AC 了,但是我随机造了个数据,就本地寄了。
如果数据错了请提醒一下,谢谢。
input:
1
2
正常应该是 0,但是我的程序没有输出。
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back()
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
const int maxlen=40005;
struct Big_Integer{
int bit[maxlen];
int len=0;
Big_Integer(int _init=0){
while(_init){
++len;
bit[len]=_init%10;
_init/=10;
}
}
Big_Integer(char* s){
len=strlen(s+1);
for(int i=1;i<=len;i++){
bit[i]=s[len-i+1]-'0';
}
}
Big_Integer operator*(const int b)const{
Big_Integer res;
res.len=len;
FOR(i,1,len){
res.bit[i]=bit[i]*b;
}
FOR(i,1,len-1){
res.bit[i+1]+=res.bit[i]/10;
res.bit[i]%=10;
}
while(res.bit[len]>=10){
res.bit[len+1]=res.bit[len]/10;
res.bit[len]%=10;
res.len++;
}
return res;
}
Big_Integer operator/(const Big_Integer& b)const{
Big_Integer vis;
Big_Integer self;
self.len=len;
FOR(i,1,len)self.bit[i]=bit[i];
FOR(i,len+1,len+b.len-1)self.bit[i]=0;
Big_Integer temp;// 暂时保存乘法结果
Big_Integer res;
if(len<b.len)return res;
for(int i=len-b.len+1;i>=1;i--){
// 从高位到低位枚举答案
// 目前是 i 位
for(int num=9;num>=0;num--){
// 枚举答案 i 位的值 num
FOR(j,1,b.len){
// 枚举 b 第 j 位
temp.bit[i+j-1]=b.bit[j]*num;
}
FOR(pos,i,i+b.len-2){
temp.bit[pos+1]+=temp.bit[pos]/10;
temp.bit[pos]%=10;
}
int pos=i+b.len-1;
while(temp.bit[pos]>=10){
temp.bit[pos+1]=temp.bit[pos]/10;
temp.bit[pos]%=10;
pos++;
}
// pos 是 temp 最高位
// temp 存储了 i 位与 b 的乘法结果,然后 self 将试着减去它
vis.bit[pos+1]=self.bit[pos+1];
FOR(j,i,pos)vis.bit[j]=self.bit[j];
FOR(j,i,pos){
if(temp.bit[j]<=self.bit[j]){
self.bit[j]-=temp.bit[j];
}else{
self.bit[j]+=10;
self.bit[j]-=temp.bit[j];
self.bit[j+1]-=1;// 不足,借位
}
}
if(self.bit[pos+1]<0){
// 不可以
FOR(j,i,pos){
self.bit[j]=vis.bit[j];// 还原
}
self.bit[pos+1]=vis.bit[pos+1];
}else{
res.bit[i]=num;
break;
}
}
}
res.len=len-b.len+1;
while(!res.bit[res.len])res.len--;
return res;
}
};
char n[10000*4],m[40000];
int main()
{
scanf("%s",n+1);
scanf("%s",m+1);
Big_Integer _n(n),_m(m);
auto res=_n/_m;
REP(i,res.len,1){
printf("%d",res.bit[i]);
}
if(res.len==0)puts("0");
return 0;
}