大数相乘 .txt

里面包括了一些acm比赛是常用的函数

//大数相乘 
//调用形式：N.Mul(A)，返回值：N*A 
/******************************************************************/ 
例如： 
A B C 
* D E 
---------------- 
= S F G H 
+ T I J K 
---------------- 
= U V L M N 

其中，SFGH=ABC*E，TIJK=ABC*D 

而对于： 
A B C 
* E 
------------- 
= S F G H 

其中，若C*E<=0xffffffff，则H=C*E，carry(进位标志)=0 
若C*E>0xffffffff，则H=(C*E)&0xffffffff 
carry=(C*E)/0xffffffff 
若B*E+carry<=0xffffffff，则G=B*E+carry，carry=0 
若B*E+carry>0xffffffff，则G=(B*E+carry)&0xffffffff 
carry=(B*E+carry)/0xffffffff 
若A*E+carry<=0xffffffff，则F=A*E+carry，carry=0 
若A*E+carry>0xffffffff，则F=(A*E+carry)&0xffffffff 
carry=(A*E+carry)/0xffffffff 
S=carry 
/*****************************************************************/ 
CBigInt CBigInt::Mul(CBigInt& A) 
{ 
CBigInt X,Y; 
unsigned __int64 mul; 
unsigned long carry; 
for(int i=0;i<A.m_nLength;i++) 
{ 
Y.m_nLength=m_nLength; 
carry=0; 
for(int j=0;j<m_nLength;j++) 
{ 
mul=m_ulvalue[j]; 
mul=mul*A.m_ulvalue[i]+carry; 
Y.m_ulvalue[j]=(unsigned long)mul; 
carry=(unsigned long)(mul>>32); 
} 
if(carry&&(Y.m_nLength<BI_MAXLEN)) 
{ 
Y.m_nLength++; 
Y.m_ulvalue[Y.m_nLength-1]=carry; 
} 
if(Y.m_nLength<BI_MAXLEN-i) 
{ 
Y.m_nLength+=i; 
for(int k=Y.m_nLength-1;k>=i;k--)Y.m_ulvalue[k]=Y.m_ulvalue[k-i]; 
for(k=0;k<i;k++)Y.m_ulvalue[k]=0; 
} 
X.Mov(X.Add(Y)); 
} 
if(m_nSign+A.m_nSign==1)X.m_nSign=0; 
else X.m_nSign=1; 
return X; 
}