NOIP复赛复习（四）读写外挂与高精度模板
2019-11-05 14:11
读入输出挂
读入输出挂就是逐个字符地读入数据，从而让读入更加快速。输出挂的原理也是一样的，都是通过将输出数字变成输出字符以加快速度。当然输入输出外挂一般用在大量输入输出的情况下，这样性价比才高一些，否则得不偿失。
void Rd(int &res){ res=0;char p;
while(p=getchar(),p<'0');
do{
res=(res<<1)+(res<<3)+(p^48);
}while(p=getchar(),p>='0'); } void Rd(int
&res){ res=0;char p;int k=1;
while(p=getchar(),!(p>='0'&&p<='9')&&p!='-');
if(p=='-')k=-1,p=getchar();
do{
res=(res<<1)+(res<<3)+(p^48);
}while(p=getchar(),(p>='0'&&p<='9'));
res*=k; } void Pt(int x){
if(x==0)return; Pt(x/10);
putchar(x%10^48); } void Ps(int x){
if(x<0)putchar('-'),x=-x;
if(x==0)putchar('0'); else Pt(x); } 高精度算法
1、高精度加法 //只限两个非负整数相加 #include #include
#include using namespace std;
const int L=110;
string add(string a,string b)
{ string ans;
int na[L]={0},nb[L]={0};
int la=a.size(),lb=b.size();
for(int i=0;i< p="">
for(int i=0;i< p="">
int lmax=la>lb?la:lb;
for(int i=0;i
if(na[lmax]) lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans; }
int main() {
string a,b;
while(cin>>a>>b) cout<<add(a,b)<<endl; <
p=""> return 0;
} 2、高精度减法 //只限大的非负整数减小的非负整数 #include
#include #include
using namespace std;
const int L=110;
string sub(string a,string b) {
string ans;
int na[L]={0},nb[L]={0};
int la=a.size(),lb=b.size();
for(int i=0;i< p="">
for(int i=0;i< p="">
int lmax=la>lb?la:lb;
for(int i=0;i< p="">
{
na[i]-=nb[i];
if(na[i]<0) na[i]+=10,na[i+1]--;
}
while(!na[--lmax]&&lmax>0) ;lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans; }
int main() {
string a,b;
while(cin>>a>>b) cout<<sub(a,b)<<endl; <
p=""> return 0;
} 3、高精度乘法 //高精度乘法a,b,均为非负整数 #include
#include #include
using namespace std;
const int L=110;
string mul(string a,string b)
{ string s;
int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();/
fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
for(int i=1;i<=La;i++)
for(int j=1;j<=Lb;j++)
nc[i+j-1]+=na[i]*nb[j];
for(int i=1;i<=La+Lb;i++)
nc[i+1]+=nc[i]/10,nc[i]%=10;
if(nc[La+Lb]) s+=nc[La+Lb]+'0';
for(int i=La+Lb-1;i>=1;i--)
s+=nc[i]+'0';
return s; }
int main() {
string a,b;
while(cin>>a>>b) cout<<mul(a,b)<<endl; <
p=""> return 0;
} 4、高精度除法 #include #include
#include using namespace std;
const int L=110;
int sub(int *a,int *b,int La,int Lb)
{ if(La< p="">
if(La==Lb)
{
for(int i=La-1;i>=0;i--)
if(a[i]>b[i]) break;
else if(a[i]<
p=""> }
for(int i=0;i< p="">
{
a[i]-=b[i];
if(a[i]<0) a[i]+=10,a[i+1]--;
}
for(int i=La-1;i>=0;i--)
if(a[i]) return i+1;
return 0;
}
string div(string n1,string n2,int nn)
{ string s,v;
int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;
fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);
for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';
for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';
if(La< p="">
//cout<<0<<endl; <
p="">
return n1;}
int t=La-Lb;
for(int i=La-1;i>=0;i--)
if(i>=t) b[i]=b[i-t];
else b[i]=0;
Lb=La;
for(int j=0;j<=t;j++)
{
int temp;
while((temp=sub(a,b+j,La,Lb-j))>=0)
{
La=temp;
r[t-j]++;
}
}
for(i=0;i
while(!r[i]) i--;
while(i>=0) s+=r[i--]+'0';
//cout<<s<<endl; <
p=""> i=tp;
while(!a[i]) i--;
while(i>=0) v+=a[i--]+'0';
if(v.empty()) v="0";
//cout<<v<<endl; <
p="">
if(nn==1) return s;
if(nn==2) return v;
} int main() {
string a,b;
while(cin>>a>>b) cout<<div(a,b,1)<<endl; <
p=""> return 0;
}
--end--
声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com
