大数求模 .txt

来自「里面包括了一些acm比赛是常用的函数」· 文本 代码 · 共 42 行

//大数求模 
//调用形式：N.Mod(A)，返回值：N%A 
//求模与求商原理相同 
CBigInt CBigInt::Mod(CBigInt& A) 
{ 
CBigInt X,Y; 
int len; 
unsigned __int64 num,div; 
unsigned long carry=0; 
X.Mov(*this); 
while(X.Cmp(A)>0) 
{ 
if(X.m_ulvalue[X.m_nLength-1]>A.m_ulvalue[A.m_nLength-1]) 
{ 
len=X.m_nLength-A.m_nLength; 
div=X.m_ulvalue[X.m_nLength-1]/(A.m_ulvalue[A.m_nLength-1]+1); 
} 
else if(X.m_nLength>A.m_nLength) 
{ 
len=X.m_nLength-A.m_nLength-1; 
num=X.m_ulvalue[X.m_nLength-1]; 
num=(num<<32)+X.m_ulvalue[X.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.Sub(A)); 
break; 
} 
Y.Mov(div); 
Y.Mov(Y.Mul(A)); 
Y.m_nLength+=len; 
for(int i=Y.m_nLength-1;i>=len;i--)Y.m_ulvalue[i]=Y.m_ulvalue[i-len]; 
for(i=0;i<len;i++)Y.m_ulvalue[i]=0; 
X.Mov(X.Sub(Y)); 
} 
if(X.Cmp(A)==0)X.Mov(0); 
return X; 
}