高精乘模板

川长思鸟来 2022-04-11 14:38 178阅读 0赞

板子

int mul(int a,int b){
    	  int xx[1150],yy[1150],x[1150],y[1150];
          int lx=1,ly=1,len;
          memset(temp,0,sizeof(temp));//初始化为0 
          while(a/10) {
          	 xx[lx++]=a%10;a/=10;
          }
          xx[lx]=a;  //xx数组倒叙存放a 
          
          while(b/10) {
          	yy[ly++]=b%10;b/=10;
          }
          yy[ly]=b;  //yy数组倒叙存放b 
          
          len=lx+ly-1;
          for(int i=1;i<=lx;i++) x[i]=xx[lx+1-i];  //x正序存放a 
          for(int i=1;i<=ly;i++) y[i]=yy[ly+1-i];  //y正序存放b 
          
          for(int i=1;i<=ly;i++){   //累乘 
          	for(int j=1;j<=lx;j++)
    		    temp[i+j-1]+=y[i]*x[j]; //结果正序存放 
    	  }
    	  for(int i=len;i>=1;i--){//大10进位 因为是正序存放所以需要从最后开始向前进位 
    	  	 temp[i-1]+=temp[i]/10;
    	  	 temp[i]%=10;
    	  } 
    	  return len;
    }

加主函数测试

#include<iostream>
    #include<cstring>
    using namespace std;
    int a,b,temp[1150];
    
    int main(){
    	cin>>a>>b;
    	int len=mul(a,b);
    	if(temp[0]!=0) cout<<temp[0];//特判 
    	for(int i=1;i<=len;i++)
    	cout<<temp[i];	  
    	return 0;
    }

改进版  主函数不需要特判

int mul(int a,int b){
    	  int xx[1150],yy[1150];
          int lx=1,ly=1,len;
          memset(temp,0,sizeof(temp));//初始化为0 
          while(a/10) {
          	 xx[lx++]=a%10;a/=10;
          }
          xx[lx]=a;  //xx数组倒叙存放a 
          
          while(b/10) {
          	yy[ly++]=b%10;b/=10;
          }
          yy[ly]=b;  //yy数组倒叙存放b 
          
          len=lx+ly-1;
    
          
          for(int i=1;i<=ly;i++){   //累乘 
          	for(int j=1;j<=lx;j++)
    		    temp[i+j-1]+=yy[i]*xx[j]; //结果倒叙存放 
    	  }
    	  for(int i=1;i<=len;i++){
    	  	 temp[i+1]+=temp[i]/10;
    	  	 temp[i]%=10;
    	  } 
    	  
    
    	  int i=1;//前后交换 
    	  if(temp[len+1]>0) {//最高位进位 
    	  	 while(i<=(len+1)/2){
    	  	 	swap(temp[i],temp[len+2-i]);
    	  	     i++;
    		   }
    		 return len+1;
    	  }
    	  else{//不进位 
    	  	while(i<=len/2){
    	  		swap(temp[i],temp[len+1-i]);
    	  		i++;
    		  }
    	  	return len;
    	  }	  
    }