大数相除 .txt

acm 做题和编程时常用的一些算法

//大数相除 
//调用形式：N.Div(A)，返回值：N/A 
//除法的关键在于“试商”，然后就变成了乘法和减法 
//这里将被除数与除数的试商转化成了被除数最高位与除数最高位的试商 
CBigInt CBigInt::Div(CBigInt& A) 
{ 
CBigInt X,Y,Z; 
int len; 
unsigned __int64 num,div; 
unsigned long carry=0; 
Y.Mov(*this); 
while(Y.Cmp(A)>0) 
{ 
if(Y.m_ulvalue[Y.m_nLength-1]>A.m_ulvalue[A.m_nLength-1]) 
{ 
len=Y.m_nLength-A.m_nLength; 
div=Y.m_ulvalue[Y.m_nLength-1]/(A.m_ulvalue[A.m_nLength-1]+1); 
} 
else if(Y.m_nLength>A.m_nLength) 
{ 
len=Y.m_nLength-A.m_nLength-1; 
num=Y.m_ulvalue[Y.m_nLength-1]; 
num=(num<<32)+Y.m_ulvalue[Y.m_nLength-2]; 
if(A.m_ulvalue[A.m_nLength-1]==0xffffffff)div=(num>>32); 
else div=num/(A.m_ulvalue[A.m_nLength-1]+1); 
} 
else 
{ 
X.Mov(X.Add(1)); 
break; 
} 
Z.Mov(div); 
Z.m_nLength+=len; 
for(int i=Z.m_nLength-1;i>=len;i--)Z.m_ulvalue[i]=Z.m_ulvalue[i-len]; 
for(i=0;i<len;i++)Z.m_ulvalue[i]=0; 
X.Mov(X.Add(Z)); 
Z.Mov(Z.Mul(A)); 
Y.Mov(Y.Sub(Z)); 
} 
if(Y.Cmp(A)==0)X.Mov(X.Add(1)); 
if(m_nSign+A.m_nSign==1)X.m_nSign=0; 
else X.m_nSign=1; 
return X; 
}