读入输出挂
读入输出挂就是逐个字符地读入数据,从而让读入更加快速。输出挂的原理也是一样的,都是通过将输出数字变成输出字符以加快速度。当然输入输出外挂一般用在大量输入输出的情况下,这样性价比才高一些,否则得不偿失。
void Rd(int &res){
res=0;char p;
while(p=getchar(),p<>
do{
res=(res<><>
}while(p=getchar(),p>='0');
}
void Rd(int &res){
res=0;char p;int k=1;
while(p=getchar(),!(p>='0'&&p<>
if(p=='-')k=-1,p=getchar();
do{
res=(res<><>
}while(p=getchar(),(p>='0'&&p<>
res*=k;
}
void Pt(int x){
if(x==0)return;
Pt(x/10);
putchar(x%10^48);
}
void Ps(int x){
if(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<>
for(int i=0;i<>
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<><>
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<>
for(int i=0;i<>
int lmax=la>lb?la:lb;
for(int i=0;i<>
{
na[i]-=nb[i];
if(na[i]<>
}
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<><>
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<>
for(int j=1;j<>
nc[i+j-1]+=na[i]*nb[j];
for(int i=1;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<><>
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<>
if(La==Lb)
{
for(int i=La-1;i>=0;i--)
if(a[i]>b[i]) break;
else if(a[i]<>
}
for(int i=0;i<>
{
a[i]-=b[i];
if(a[i]<>
}
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<><>
//cout<><>
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<>
{
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<><>
i=tp;
while(!a[i]) i--;
while(i>=0) v+=a[i--]+'0';
if(v.empty()) v='0';
//cout<><>
if(nn==1) return s;
if(nn==2) return v;
}
int main()
{
string a,b;
while(cin>>a>>b) cout<><>
return 0;
}
长沙信息学竞赛
联系客服