P2005 A/B Problem II - 华师一附中OI组

#include <bits/stdc++.h>
using namespace std;
string A,B,C; //A/B=C
string B09[10]; // 除数的0-9倍
bool isbig(string X,string Y) //字符串当数字比较大小
{
int lx=X.size(),ly=Y.size();
return (lx>ly)||(lx==ly && X>=Y);
}
string add(string A,string B) //基本高精加
{
string C="";
if (A.size()<B.size()) swap(A,B);
int la=A.size(),lb=B.size(),i;
for (i=lb+1; i<=la; i++) B="0"+B;
int j=0;
for (i=la-1; i>=0; i--)
{
int x=A[i]-'0'+B[i]-'0'+j;
j=x/10;
x=x%10;
C=char(x+'0')+C;
}
if (j) C="1"+C;
return C;
}
string sub(string A,string B) //基本高精减
{
string C="";
int la=A.size(),lb=B.size(),i,j=0,x;
for (i=lb+1; i<=la; i++) B="0"+B;
for (i=la-1; i>=0; i--)
{
x=A[i]-B[i]-j;
if (x<0)
{
j=1;
x+=10;
}
else j=0;
C=char(x+'0')+C;
}
int p=0;
while (C[p]=='0' && p<la-1) p++;
return C.substr(p);
}
void CB09(string B)
{
B09[0]="0",B09[1]=B;
for (int i=2; i<=9; i++)B09[i]=add(B09[i-1],B);
///for (int i=0; i<=9; i++) cout<<B09[i]<<endl;
}
int main()
{
cin>>A>>B;
CB09(B);
int la=A.size(),lb=B.size(),p;
string TA=A.substr(0,lb);
if (isbig(TA,B)) p=lb;
else
{
TA=TA+A[lb];
p=lb+1;
}
for(; p<=la; p++)
{
int k=9;
while (!isbig(TA,B09[k]))k--;
C=C+char(k+'0');
//cout<<TA<<' '<<C<<endl;
TA=sub(TA,B09[k]);
//cout<<TA<<endl;
TA=TA+A[p];
while (TA[0]=='0' && TA.size()>1) TA.erase(0,1);//去前面的0
}
cout<<C;
return 0;
}

复制代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL A,B,C,L,R,M,ANS;
int main()
{
cin>>A>>B;
L=0;
R=6227020800l;
while (L<=R)
{
M=(L+R)/2;
X=M*B;
if (X<=A)
{
ANS=M;
L=M+1;
}
else if (X>A) R=M-1;
}
cout<<ANS;
return 0;
}

复制代码

#include <bits/stdc++.h>
using namespace std;
struct BigNum
{
int l;//位数
int a[22000];
BigNum()//初始化
{
memset(a,sizeof(a),0);
l=1;
}
void pp() //输出
{
for (int i=l-1; i>=0; i--) cout<<a[i];
cout<<' ';
}
} A,B,C,L,R,M,X,ANS;
bool operator <= (BigNum A,BigNum B)// 大的比大的
{
if(A.l>B.l) return 0;
if(A.l<B.l) return 1;
for (int i=A.l-1; i>=0; i--) // 这个比较精妙
if (A.a[i]<B.a[i]) return 1;
else if (A.a[i]>B.a[i]) return 0;
return 1;
}
BigNum operator * (BigNum A,BigNum B)// 大的乘大的
{
BigNum C;
int i,j,x;
C.l=A.l+B.l;
for (i=0; i<=C.l-1; i++) C.a[i]=0;
for (i=0; i<=A.l-1; i++)
for (j=0; j<=B.l-1; j++)
C.a[i+j]+=A.a[i]*B.a[j];
for (i=0; i<=C.l-1; i++)
{
x=C.a[i];
C.a[i]=x%10;
C.a[i+1]+=x/10;
}
while (C.a[C.l-1]==0 && C.l>1) C.l--;
return C;
}
BigNum operator + (BigNum A,BigNum B)// 大的加大的
{
if (A.l<B.l) swap(A,B);
int x,i;
for (i=0; i<=B.l-1; i++) A.a[i]+=B.a[i];
for (i=0; i<=A.l-1; i++)
{
x=A.a[i];
A.a[i]=x%10;
A.a[i+1]+=x/10;
}
if (A.a[A.l]>0)A.l++;
return A;
}
BigNum operator + (BigNum A,int b)
{
int x,i;
A.a[0]+=b;
for (i=0; i<=A.l-1; i++)
{
x=A.a[i];
A.a[i]=x%10;
A.a[i+1]+=x/10;
}
if (A.a[A.l]>0) A.l++;
return A;
}
BigNum operator - (BigNum A,int b)
{
int x,i;
A.a[0]-=b;
for (i=0; i<=A.l-1; i++)
{
x=A.a[i];
if (x<0) //这个我觉得写的很好
{
A.a[i]=x%10+10;
A.a[i+1]+=(x/10-1);
}
}
while (A.a[A.l-1]==0 && A.l>0) A.l--;
return A;
}
BigNum operator / (BigNum A,int b)
{
int i,x=0;
for (i=A.l-1; i>=0; i--)
{
x=10*x+A.a[i];
A.a[i]=x/b;
x=x%b;
}
while (A.a[A.l-1]==0 && A.l>0) A.l--;
return A;
}
BigNum Ch(string s)
{
int l=s.size();
BigNum A;
A.l=l;
for (int i=0; i<=l; i++) A.a[i]=s[l-1-i]-'0';
return A;
}
int main()
{
string sa,sb;
cin>>sa>>sb;
A=Ch(sa),B=Ch(sb);
L=Ch("0"),R=Ch("99999999999");
while (L<=R)
{
M=(R+L)/2;
X=M*B;
//L.pp(),R.pp(),M.pp(),X.pp();
//cout<<endl;
if (X<=A)
{
ANS=M;
L=M+1;
}
else R=M-1;
}
ANS.pp();
return 0;
}

复制代码