记录编号	299622	评测结果	AAAAAAAAAA
题目名称	增强的除法问题	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2016-08-26 16:10:43	内存使用	0.27 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define copy(a,b) memcpy(a,b,sizeof(int)*maxn)
using namespace std;
const int maxn=410,ONE[maxn]={1,1,0};
void input(int*);
void output(const int*);
int cmp(const int*,const int*);
void plus(const int*,const int*,int*);
void subt(const int*,const int*,int*);
void multi(const int*,const int*,int*);
void divide2(const int*,int*);
int MAIN();
char s[maxn];
int a[maxn],b[maxn],d[maxn],ans[maxn],l[maxn]={0},r[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("div.in","r",stdin);
	freopen("div.out","w",stdout);
#endif
	input(a);
	input(b);
	if(cmp(a,b)<0)printf("0");
	else{
			plus(a,ONE,r);
		while(cmp(l,r)<0){
			plus(l,r,d);
			divide2(d,ans);
			multi(ans,b,d);
			if(cmp(d,a)<=0)plus(ans,ONE,l);
			else subt(ans,ONE,r);
		}
		subt(l,ONE,d);
		output(d);
	}
	return 0;
}
void input(int* a){
	memset(a,0,sizeof(int)*maxn);
	scanf("%s",s);
	a[0]=strlen(s);
	for(int i=0;i<a[0];i++)a[a[0]-i]=s[i]-'0';
	if(!a[a[0]])a[0]--;
}
void output(const int* a){
	if(!a[0])putchar('0');
	else for(int i=a[0];i;i--)printf("%d",a[i]);
}
int cmp(const int* a,const int* b){
	if(a[0]!=b[0])return a[0]-b[0];
	for(int i=a[0];i;i--)if(a[i]!=b[i])return a[i]-b[i];
	return 0;
}
void plus(const int* a,const int* b,int* c){
	memset(c,0,sizeof(int)*maxn);
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=c[0];i++){
		c[i]+=a[i]+b[i];
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	if(c[c[0]+1])c[0]++;
}
void subt(const int* a,const int* b,int* c){
	memset(c,0,sizeof(int)*maxn);
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=c[0];i++){
		c[i]+=a[i]-b[i];
		if(c[i]<0){
			c[i+1]--;
			c[i]+=10;
		}
	}
	if(!c[c[0]])c[0]--;
}
void multi(const int* a,const int* b,int* c){
	memset(c,0,sizeof(int)*maxn);
	if(!a[0]||!b[0])return;
	c[0]=a[0]+b[0];
	for(int i=1;i<=a[0];i++)for(int j=1;j<=b[0];j++){
		c[i+j-1]+=a[i]*b[j];
		c[i+j]+=c[i+j-1]/10;
		c[i+j-1]%=10;
	}
	if(!c[c[0]])c[0]--;
}
void divide2(const int* a,int* c){
	memset(c,0,sizeof(int)*maxn);
	copy(c,a);
	for(int i=c[0];i;i--){
		if(i>1&&(c[i]&1))c[i-1]+=10;
		c[i]>>=1;
	}
	if(!c[c[0]])c[0]--;
}