大数模板
发布时间：2020-12-14 03:03:46 所属栏目：大数据 来源：网络整理
导读：要好好研究一下。。。。。。。 模板一： #include iostream #include cstring using namespace std; #define DIGIT 4 //四位隔开,即万进制 #define DEPTH 10000 //万进制 #define MAX 251 //题目最大位数/4，要不大直接设为最大位数也行 typedef int bignum_
|
要好好研究一下。。。。。。。 模板一： #include <iostream>
#include <cstring>
using namespace std;
#define DIGIT 4 //四位隔开,即万进制
#define DEPTH 10000 //万进制
#define MAX 251 //题目最大位数/4，要不大直接设为最大位数也行
typedef int bignum_t[MAX+1];
/************************************************************************/
/* 读取操作数，对操作数进行处理存储在数组里 */
/************************************************************************/
int read(bignum_t a,istream&is=cin)
{
char buf[MAX*DIGIT+1],ch ;
int i,j ;
memset((void*)a,sizeof(bignum_t));
if(!(is>>buf))return 0 ;
for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)
ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;
for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');
for(i=1;i<=a[0];i++)
for(a[i]=0,j=0;j<DIGIT;j++)
a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0' ;
for(;!a[a[0]]&&a[0]>1;a[0]--);
return 1 ;
}
void write(const bignum_t a,ostream&os=cout)
{
int i,j ;
for(os<<a[i=a[0]],i--;i;i--)
for(j=DEPTH/10;j;j/=10)
os<<a[i]/j%10 ;
}
int comp(const bignum_t a,const bignum_t b)
{
int i ;
if(a[0]!=b[0])
return a[0]-b[0];
for(i=a[0];i;i--)
if(a[i]!=b[i])
return a[i]-b[i];
return 0 ;
}
int comp(const bignum_t a,const int b)
{
int c[12]=
{
1
}
;
for(c[1]=b;c[c[0]]>=DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);
return comp(a,c);
}
int comp(const bignum_t a,const int c,const int d,const bignum_t b)
{
int i,t=0,O=-DEPTH*2 ;
if(b[0]-a[0]<d&&c)
return 1 ;
for(i=b[0];i>d;i--)
{
t=t*DEPTH+a[i-d]*c-b[i];
if(t>0)return 1 ;
if(t<O)return 0 ;
}
for(i=d;i;i--)
{
t=t*DEPTH-b[i];
if(t>0)return 1 ;
if(t<O)return 0 ;
}
return t>0 ;
}
/************************************************************************/
/* 大数与大数相加 */
/************************************************************************/
void add(bignum_t a,const bignum_t b)
{
int i ;
for(i=1;i<=b[0];i++)
if((a[i]+=b[i])>=DEPTH)
a[i]-=DEPTH,a[i+1]++;
if(b[0]>=a[0])
a[0]=b[0];
else
for(;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);
a[0]+=(a[a[0]+1]>0);
}
/************************************************************************/
/* 大数与小数相加 */
/************************************************************************/
void add(bignum_t a,const int b)
{
int i=1 ;
for(a[1]+=b;a[i]>=DEPTH&&i<a[0];a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);
for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
}
/************************************************************************/
/* 大数相减(被减数>=减数) */
/************************************************************************/
void sub(bignum_t a,const bignum_t b)
{
int i ;
for(i=1;i<=b[0];i++)
if((a[i]-=b[i])<0)
a[i+1]--,a[i]+=DEPTH ;
for(;a[i]<0;a[i]+=DEPTH,a[i]--);
for(;!a[a[0]]&&a[0]>1;a[0]--);
}
/************************************************************************/
/* 大数减去小数(被减数>=减数) */
/************************************************************************/
void sub(bignum_t a,const int b)
{
int i=1 ;
for(a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);
for(;!a[a[0]]&&a[0]>1;a[0]--);
}
void sub(bignum_t a,const bignum_t b,const int d)
{
int i,O=b[0]+d ;
for(i=1+d;i<=O;i++)
if((a[i]-=b[i-d]*c)<0)
a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH ;
for(;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,i++);
for(;!a[a[0]]&&a[0]>1;a[0]--);
}
/************************************************************************/
/* 大数相乘，读入被乘数a，乘数b，结果保存在c[] */
/************************************************************************/
void mul(bignum_t c,const bignum_t a,j ;
memset((void*)c,sizeof(bignum_t));
for(c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)
for(j=1;j<=b[0];j++)
if((c[i+j-1]+=a[i]*b[j])>=DEPTH)
c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH ;
for(c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);
}
/************************************************************************/
/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数 */
/************************************************************************/
void mul(bignum_t a,const int b)
{
int i ;
for(a[1]*=b,i=2;i<=a[0];i++)
{
a[i]*=b ;
if(a[i-1]>=DEPTH)
a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH ;
}
for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[0]++);
for(;!a[a[0]]&&a[0]>1;a[0]--);
}
void mul(bignum_t b,const int d)
{
int i ;
memset((void*)b,sizeof(bignum_t));
for(b[0]=a[0]+d,i=d+1;i<=b[0];i++)
if((b[i]+=a[i-d]*c)>=DEPTH)
b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH ;
for(;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);
for(;!b[b[0]]&&b[0]>1;b[0]--);
}
/**************************************************************************/
/* 大数相除,读入被除数a，除数b，结果保存在c[]数组 */
/* 需要comp()函数 */
/**************************************************************************/
void div(bignum_t c,bignum_t a,const bignum_t b)
{
int h,l,m,i ;
memset((void*)c,sizeof(bignum_t));
c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1 ;
for(i=c[0];i;sub(a,b,c[i]=m,i-1),i--)
for(h=DEPTH-1,l=0,m=(h+l+1)>>1;h>l;m=(h+l+1)>>1)
if(comp(b,i-1,a))h=m-1 ;
else l=m ;
for(;!c[c[0]]&&c[0]>1;c[0]--);
c[0]=c[0]>1?c[0]:1 ;
}
void div(bignum_t a,const int b,int&c)
{
int i ;
for(c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);
for(;!a[a[0]]&&a[0]>1;a[0]--);
}
/************************************************************************/
/* 大数平方根，读入大数a，结果保存在b[]数组里 */
/* 需要comp()函数 */
/************************************************************************/
void sqrt(bignum_t b,bignum_t a)
{
int h,i ;
memset((void*)b,sizeof(bignum_t));
for(i=b[0]=(a[0]+1)>>1;i;sub(a,b[i]+=m,b[i]=m=(h+l+1)>>1;h>l;b[i]=m=(h+l+1)>>1)
if(comp(b,a))h=m-1 ;
else l=m ;
for(;!b[b[0]]&&b[0]>1;b[0]--);
for(i=1;i<=b[0];b[i++]>>=1);
}
/************************************************************************/
/* 返回大数的长度 */
/************************************************************************/
int length(const bignum_t a)
{
int t,ret ;
for(ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);
return ret>0?ret:1 ;
}
/************************************************************************/
/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数 */
/************************************************************************/
int digit(const bignum_t a,const int b)
{
int i,ret ;
for(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);
return ret%10 ;
}
/************************************************************************/
/* 返回大数末尾0的个数 */
/************************************************************************/
int zeronum(const bignum_t a)
{
int ret,t ;
for(ret=0;!a[ret+1];ret++);
for(t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++);
return ret ;
}
void comp(int*a,const int l,const int h,j,t ;
for(i=l;i<=h;i++)
for(t=i,j=2;t>1;j++)
while(!(t%j))
a[j]+=d,t/=j ;
}
void convert(int*a,bignum_t b)
{
int i,t=1 ;
memset(b,sizeof(bignum_t));
for(b[0]=b[1]=1,i=2;i<=h;i++)
if(a[i])
for(j=a[i];j;t*=i,j--)
if(t*i>DEPTH)
mul(b,t),t=1 ;
mul(b,t);
}
/************************************************************************/
/* 组合数 */
/************************************************************************/
void combination(bignum_t a,int m,int n)
{
int*t=new int[m+1];
memset((void*)t,sizeof(int)*(m+1));
comp(t,n+1,1);
comp(t,2,m-n,-1);
convert(t,a);
delete[]t ;
}
/************************************************************************/
/* 排列数 */
/************************************************************************/
void permutation(bignum_t a,int n)
{
int i,t=1 ;
memset(a,sizeof(bignum_t));
a[0]=a[1]=1 ;
for(i=m-n+1;i<=m;t*=i++)
if(t*i>DEPTH)
mul(a,t=1 ;
mul(a,t);
}
#define SGN(x) ((x)>0?1:((x)<0?-1:0))
#define ABS(x) ((x)>0?(x):-(x))
int read(bignum_t a,int&sgn,istream&is=cin)
{
char str[MAX*DIGIT+2],ch,*buf ;
int i,sizeof(bignum_t));
if(!(is>>str))return 0 ;
buf=str,sgn=1 ;
if(*buf=='-')sgn=-1,buf++;
for(a[0]=strlen(buf),j=0;j<DIGIT;j++)
a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0' ;
for(;!a[a[0]]&&a[0]>1;a[0]--);
if(a[0]==1&&!a[1])sgn=0 ;
return 1 ;
}
struct bignum
{
bignum_t num ;
int sgn ;
public :
inline bignum()
{
memset(num,sizeof(bignum_t));
num[0]=1 ;
sgn=0 ;
}
inline int operator!()
{
return num[0]==1&&!num[1];
}
inline bignum&operator=(const bignum&a)
{
memcpy(num,a.num,sizeof(bignum_t));
sgn=a.sgn ;
return*this ;
}
inline bignum&operator=(const int a)
{
memset(num,sizeof(bignum_t));
num[0]=1 ;
sgn=SGN (a);
add(num,sgn*a);
return*this ;
}
;
inline bignum&operator+=(const bignum&a)
{
if(sgn==a.sgn)add(num,a.num);
else if
(sgn&&a.sgn)
{
int ret=comp(num,a.num);
if(ret>0)sub(num,a.num);
else if(ret<0)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memcpy(num,sizeof(bignum_t));
sub (num,t);
sgn=a.sgn ;
}
else memset(num,sizeof(bignum_t)),num[0]=1,sgn=0 ;
}
else if(!sgn)
memcpy(num,sgn=a.sgn ;
return*this ;
}
inline bignum&operator+=(const int a)
{
if(sgn*a>0)add(num,ABS(a));
else if(sgn&&a)
{
int ret=comp(num,ABS(a));
if(ret>0)sub(num,ABS(a));
else if(ret<0)
{
bignum_t t ;
memcpy(t,sizeof(bignum_t));
memset(num,sizeof(bignum_t));
num[0]=1 ;
add(num,ABS (a));
sgn=-sgn ;
sub(num,t);
}
else memset(num,sgn=0 ;
}
else if
(!sgn)sgn=SGN(a),add(num,ABS(a));
return*this ;
}
inline bignum operator+(const bignum&a)
{
bignum ret ;
memcpy(ret.num,sizeof (bignum_t));
ret.sgn=sgn ;
ret+=a ;
return ret ;
}
inline bignum operator+(const int a)
{
bignum ret ;
memcpy(ret.num,sizeof (bignum_t));
ret.sgn=sgn ;
ret+=a ;
return ret ;
}
inline bignum&operator-=(const bignum&a)
{
if(sgn*a.sgn<0)add(num,sizeof(bignum_t));
sub(num,t);
sgn=-sgn ;
}
else memset(num,sgn=0 ;
}
else if(!sgn)add (num,a.num),sgn=-a.sgn ;
return*this ;
}
inline bignum&operator-=(const int a)
{
if(sgn*a<0)add(num,ABS(a));
sub(num,sgn=0 ;
}
else if
(!sgn)sgn=-SGN(a),ABS(a));
return*this ;
}
inline bignum operator-(const bignum&a)
{
bignum ret ;
memcpy(ret.num,sizeof(bignum_t));
ret.sgn=sgn ;
ret-=a ;
return ret ;
}
inline bignum operator-(const int a)
{
bignum ret ;
memcpy(ret.num,sizeof(bignum_t));
ret.sgn=sgn ;
ret-=a ;
return ret ;
}
inline bignum&operator*=(const bignum&a)
{
bignum_t t ;
mul(t,a.num);
memcpy(num,t,sizeof(bignum_t));
sgn*=a.sgn ;
return*this ;
}
inline bignum&operator*=(const int a)
{
mul(num,ABS(a));
sgn*=SGN(a);
return*this ;
}
inline bignum operator*(const bignum&a)
{
bignum ret ;
mul(ret.num,a.num);
ret.sgn=sgn*a.sgn ;
return ret ;
}
inline bignum operator*(const int a)
{
bignum ret ;
memcpy(ret.num,sizeof (bignum_t));
mul(ret.num,ABS(a));
ret.sgn=sgn*SGN(a);
return ret ;
}
inline bignum&operator/=(const bignum&a)
{
bignum_t t ;
div(t,a.num);
memcpy (num,sizeof(bignum_t));
sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn ;
return*this ;
}
inline bignum&operator/=(const int a)
{
int t ;
div(num,ABS(a),t);
sgn=(num[0]==1&&!num [1])?0:sgn*SGN(a);
return*this ;
}
inline bignum operator/(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(t,sizeof(bignum_t));
div(ret.num,a.num);
ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn ;
return ret ;
}
inline bignum operator/(const int a)
{
bignum ret ;
int t ;
memcpy(ret.num,t);
ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a);
return ret ;
}
inline bignum&operator%=(const bignum&a)
{
bignum_t t ;
div(t,a.num);
if(num[0]==1&&!num[1])sgn=0 ;
return*this ;
}
inline int operator%=(const int a)
{
int t ;
div(num,t);
memset(num,sizeof (bignum_t));
num[0]=1 ;
add(num,t);
return t ;
}
inline bignum operator%(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(ret.num,sizeof(bignum_t));
div(t,ret.num,a.num);
ret.sgn=(ret.num[0]==1&&!ret.num [1])?0:sgn ;
return ret ;
}
inline int operator%(const int a)
{
bignum ret ;
int t ;
memcpy(ret.num,t);
memset(ret.num,sizeof(bignum_t));
ret.num[0]=1 ;
add(ret.num,t);
return t ;
}
inline bignum&operator++()
{
*this+=1 ;
return*this ;
}
inline bignum&operator--()
{
*this-=1 ;
return*this ;
}
;
inline int operator>(const bignum&a)
{
return sgn>0?(a.sgn>0?comp(num,a.num)>0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<0:0):a.sgn<0);
}
inline int operator>(const int a)
{
return sgn>0?(a>0?comp(num,a)>0:1):(sgn<0?(a<0?comp(num,-a)<0:0):a<0);
}
inline int operator>=(const bignum&a)
{
return sgn>0?(a.sgn>0?comp(num,a.num)>=0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<=0:0):a.sgn<=0);
}
inline int operator>=(const int a)
{
return sgn>0?(a>0?comp(num,a)>=0:1):(sgn<0?(a<0?comp(num,-a)<=0:0):a<=0);
}
inline int operator<(const bignum&a)
{
return sgn<0?(a.sgn<0?comp(num,a.num)>0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<0:0):a.sgn>0);
}
inline int operator<(const int a)
{
return sgn<0?(a<0?comp(num,-a)>0:1):(sgn>0?(a>0?comp(num,a)<0:0):a>0);
}
inline int operator<=(const bignum&a)
{
return sgn<0?(a.sgn<0?comp(num,a.num)>=0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<=0:0):a.sgn>=0);
}
inline int operator<=(const int a)
{
return sgn<0?(a<0?comp(num,-a)>=0:1):
(sgn>0?(a>0?comp(num,a)<=0:0):a>=0);
}
inline int operator==(const bignum&a)
{
return(sgn==a.sgn)?!comp(num,a.num):0 ;
}
inline int operator==(const int a)
{
return(sgn*a>=0)?!comp(num,ABS(a)):0 ;
}
inline int operator!=(const bignum&a)
{
return(sgn==a.sgn)?comp(num,a.num):1 ;
}
inline int operator!=(const int a)
{
return(sgn*a>=0)?comp(num,ABS(a)):1 ;
}
inline int operator[](const int a)
{
return digit(num,a);
}
friend inline istream&operator>>(istream&is,bignum&a)
{
read(a.num,a.sgn,is);
return is ;
}
friend inline ostream&operator<<(ostream&os,const bignum&a)
{
if(a.sgn<0)
os<<'-' ;
write(a.num,os);
return os ;
}
friend inline bignum sqrt(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(t,sizeof(bignum_t));
sqrt(ret.num,t);
ret.sgn=ret.num[0]!=1||ret.num[1];
return ret ;
}
friend inline bignum sqrt(const bignum&a,bignum&b)
{
bignum ret ;
memcpy(b.num,b.num);
ret.sgn=ret.num[0]!=1||ret.num[1];
b.sgn=b.num[0]!=1||ret.num[1];
return ret ;
}
inline int length()
{
return :: length(num);
}
inline int zeronum()
{
return :: zeronum(num);
}
inline bignum C(const int m,const int n)
{
combination(num,n);
sgn=1 ;
return*this ;
}
inline bignum P(const int m,const int n)
{
permutation(num,n);
sgn=1 ;
return*this ;
}
};
int main()
{
bignum a,c;
cin>>a>>b;
cout<<"加法:"<<a+b<<endl;
cout<<"减法:"<<a-b<<endl;
cout<<"乘法:"<<a*b<<endl;
cout<<"除法:"<<a/b<<endl;
c=sqrt(a);
cout<<"平方根:"<<c<<endl;
cout<<"a的长度:"<<a.length()<<endl;
cout<<"a的末尾0个数:"<<a.zeronum()<<endl<<endl;
cout<<"组合: 从10个不同元素取3个元素组合的所有可能性为"<<c.C(10,3)<<endl;
cout<<"排列: 从10个不同元素取3个元素排列的所有可能性为"<<c.P(10,3)<<endl;
return 0 ;
}
?
模板二： #include <cstdio>
#include <cstring>
#include <cstdlib>
//允许生成1120位（二进制）的中间结果
#define BI_MAXLEN 105
#define DEC 10
#define HEX 16
class CBigInt
{
public:
//大数在0x100000000进制下的长度
unsigned m_nLength;
//用数组记录大数在0x100000000进制下每一位的值
unsigned long m_ulValue[BI_MAXLEN];
CBigInt();
~CBigInt();
/*****************************************************************
基本操作与运算
Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”
Cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“<=”等
Add，加，求大数与大数或大数与普通整数的和，可重载为运算符“+”
Sub，减，求大数与大数或大数与普通整数的差，可重载为运算符“-”
Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“*”
Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“/”
Mod，模，求大数与大数或大数与普通整数的模，可重载为运算符“%”
*****************************************************************/
void Mov(unsigned __int64 A);
void Mov(CBigInt& A);
CBigInt Add(CBigInt& A);
CBigInt Sub(CBigInt& A);
CBigInt Mul(CBigInt& A);
CBigInt Div(CBigInt& A);
CBigInt Mod(CBigInt& A);
CBigInt Add(unsigned long A);
CBigInt Sub(unsigned long A);
CBigInt Mul(unsigned long A);
CBigInt Div(unsigned long A);
unsigned long Mod(unsigned long A);
int Cmp(CBigInt& A);
/*****************************************************************
输入输出
Get，从字符串按10进制或16进制格式输入到大数
Put，将大数按10进制或16进制格式输出到字符串
*****************************************************************/
void Get(char str[],unsigned int system=DEC);
void Put(char str[],unsigned int system=DEC);
/*****************************************************************
RSA相关运算
Rab，拉宾米勒算法进行素数测试
Euc，欧几里德算法求解同余方程
RsaTrans，反复平方算法进行幂模运算
GetPrime，产生指定长度的随机大素数
*****************************************************************/
int Rab();
CBigInt Euc(CBigInt& A);
CBigInt RsaTrans(CBigInt& A,CBigInt& B);
void GetPrime(int bits);
};
//小素数表
const static int PrimeTable[550]=
{ 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001
};
//构造大数对象并初始化为零
CBigInt::CBigInt()
{
m_nLength=1;
for(int i=0;i<BI_MAXLEN;i++)m_ulValue[i]=0;
}
//解构大数对象
CBigInt::~CBigInt()
{
}
/****************************************************************************************
大数比较
调用方式：N.Cmp(A)
返回值：若N<A返回-1；若N=A返回0；若N>A返回1
****************************************************************************************/
int CBigInt::Cmp(CBigInt& A)
{
if(m_nLength>A.m_nLength)return 1;
if(m_nLength<A.m_nLength)return -1;
for(int i=m_nLength-1;i>=0;i--)
{
if(m_ulValue[i]>A.m_ulValue[i])return 1;
if(m_ulValue[i]<A.m_ulValue[i])return -1;
}
return 0;
}
/****************************************************************************************
大数赋值
调用方式：N.Mov(A)
返回值：无，N被赋值为A
****************************************************************************************/
void CBigInt::Mov(CBigInt& A)
{
m_nLength=A.m_nLength;
for(int i=0;i<BI_MAXLEN;i++)m_ulValue[i]=A.m_ulValue[i];
}
void CBigInt::Mov(unsigned __int64 A)
{
if(A>0xffffffff)
{
m_nLength=2;
m_ulValue[1]=(unsigned long)(A>>32);
m_ulValue[0]=(unsigned long)A;
}
else
{
m_nLength=1;
m_ulValue[0]=(unsigned long)A;
}
for(int i=m_nLength;i<BI_MAXLEN;i++)m_ulValue[i]=0;
}
/****************************************************************************************
大数相加
调用形式：N.Add(A)
返回值：N+A
****************************************************************************************/
CBigInt CBigInt::Add(CBigInt& A)
{
CBigInt X;
X.Mov(*this);
unsigned carry=0;
unsigned __int64 sum=0;
if(X.m_nLength<A.m_nLength)X.m_nLength=A.m_nLength;
for(unsigned i=0;i<X.m_nLength;i++)
{
sum=A.m_ulValue[i];
sum=sum+X.m_ulValue[i]+carry;
X.m_ulValue[i]=(unsigned long)sum;
carry=(unsigned)(sum>>32);
}
X.m_ulValue[X.m_nLength]=carry;
X.m_nLength+=carry;
return X;
}
CBigInt CBigInt::Add(unsigned long A)
{
CBigInt X;
X.Mov(*this);
unsigned __int64 sum;
sum=X.m_ulValue[0];
sum+=A;
X.m_ulValue[0]=(unsigned long)sum;
if(sum>0xffffffff)
{
unsigned i=1;
while(X.m_ulValue[i]==0xffffffff){X.m_ulValue[i]=0;i++;}
X.m_ulValue[i]++;
if(m_nLength==i)m_nLength++;
}
return X;
}
/****************************************************************************************
大数相减
调用形式：N.Sub(A)
返回值：N-A
****************************************************************************************/
CBigInt CBigInt::Sub(CBigInt& A)
{
CBigInt X;
X.Mov(*this);
if(X.Cmp(A)<=0){X.Mov(0);return X;}
unsigned carry=0;
unsigned __int64 num;
unsigned i;
for(i=0;i<m_nLength;i++)
{
if((m_ulValue[i]>A.m_ulValue[i])||((m_ulValue[i]==A.m_ulValue[i])&&(carry==0)))
{
X.m_ulValue[i]=m_ulValue[i]-carry-A.m_ulValue[i];
carry=0;
}
else
{
num=0x100000000+m_ulValue[i];
X.m_ulValue[i]=(unsigned long)(num-carry-A.m_ulValue[i]);
carry=1;
}
}
while(X.m_ulValue[X.m_nLength-1]==0)X.m_nLength--;
return X;
}
CBigInt CBigInt::Sub(unsigned long A)
{
CBigInt X;
X.Mov(*this);
if(X.m_ulValue[0]>=A){X.m_ulValue[0]-=A;return X;}
if(X.m_nLength==1){X.Mov(0);return X;}
unsigned __int64 num=0x100000000+X.m_ulValue[0];
X.m_ulValue[0]=(unsigned long)(num-A);
int i=1;
while(X.m_ulValue[i]==0){X.m_ulValue[i]=0xffffffff;i++;}
X.m_ulValue[i]--;
if(X.m_ulValue[i]==0)X.m_nLength--;
return X;
}
/****************************************************************************************
大数相乘
调用形式：N.Mul(A)
返回值：N*A
****************************************************************************************/
CBigInt CBigInt::Mul(CBigInt& A)
{
if(A.m_nLength==1)return Mul(A.m_ulValue[0]);
CBigInt X;
unsigned __int64 sum,mul=0,carry=0;
unsigned i,j;
X.m_nLength=m_nLength+A.m_nLength-1;
for(i=0;i<X.m_nLength;i++)
{
sum=carry;
carry=0;
for(j=0;j<A.m_nLength;j++)
{
if(((i-j)>=0)&&((i-j)<m_nLength))
{
mul=m_ulValue[i-j];
mul*=A.m_ulValue[j];
carry+=mul>>32;
mul=mul&0xffffffff;
sum+=mul;
}
}
carry+=sum>>32;
X.m_ulValue[i]=(unsigned long)sum;
}
if(carry){X.m_nLength++;X.m_ulValue[X.m_nLength-1]=(unsigned long)carry;}
return X;
}
CBigInt CBigInt::Mul(unsigned long A)
{
CBigInt X;
unsigned __int64 mul;
unsigned long carry=0;
X.Mov(*this);
for(unsigned i=0;i<m_nLength;i++)
{
mul=m_ulValue[i];
mul=mul*A+carry;
X.m_ulValue[i]=(unsigned long)mul;
carry=(unsigned long)(mul>>32);
}
if(carry){X.m_nLength++;X.m_ulValue[X.m_nLength-1]=carry;}
return X;
}
/****************************************************************************************
大数相除
调用形式：N.Div(A)
返回值：N/A
****************************************************************************************/
CBigInt CBigInt::Div(CBigInt& A)
{
if(A.m_nLength==1)return Div(A.m_ulValue[0]);
CBigInt X,Y,Z;
unsigned i,len;
unsigned __int64 num,div;
Y.Mov(*this);
while(Y.Cmp(A)>=0)
{
div=Y.m_ulValue[Y.m_nLength-1];
num=A.m_ulValue[A.m_nLength-1];
len=Y.m_nLength-A.m_nLength;
if((div==num)&&(len==0)){X.Mov(X.Add(1));break;}
if((div<=num)&&len){len--;div=(div<<32)+Y.m_ulValue[Y.m_nLength-2];}
div=div/(num+1);
Z.Mov(div);
if(len)
{
Z.m_nLength+=len;
for(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));
Y.Mov(Y.Sub(A.Mul(Z)));
}
return X;
}
CBigInt CBigInt::Div(unsigned long A)
{
CBigInt X;
X.Mov(*this);
if(X.m_nLength==1){X.m_ulValue[0]=X.m_ulValue[0]/A;return X;}
unsigned __int64 div,mul;
unsigned long carry=0;
for(int i=X.m_nLength-1;i>=0;i--)
{
div=carry;
div=(div<<32)+X.m_ulValue[i];
X.m_ulValue[i]=(unsigned long)(div/A);
mul=(div/A)*A;
carry=(unsigned long)(div-mul);
}
if(X.m_ulValue[X.m_nLength-1]==0)X.m_nLength--;
return X;
}
/****************************************************************************************
大数求模
调用形式：N.Mod(A)
返回值：N%A
****************************************************************************************/
CBigInt CBigInt::Mod(CBigInt& A)
{
CBigInt X,Y;
unsigned __int64 div,num;
unsigned long carry=0;
unsigned i,len;
X.Mov(*this);
while(X.Cmp(A)>=0)
{
div=X.m_ulValue[X.m_nLength-1];
num=A.m_ulValue[A.m_nLength-1];
len=X.m_nLength-A.m_nLength;
if((div==num)&&(len==0)){X.Mov(X.Sub(A));break;}
if((div<=num)&&len){len--;div=(div<<32)+X.m_ulValue[X.m_nLength-2];}
div=div/(num+1);
Y.Mov(div);
Y.Mov(A.Mul(Y));
if(len)
{
Y.m_nLength+=len;
for(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));
}
return X;
}
unsigned long CBigInt::Mod(unsigned long A)
{
if(m_nLength==1)return(m_ulValue[0]%A);
unsigned __int64 div;
unsigned long carry=0;
for(int i=m_nLength-1;i>=0;i--)
{
div=m_ulValue[i];
div+=carry*0x100000000;
carry=(unsigned long)(div%A);
}
return carry;
}
/****************************************************************************************
从字符串按10进制或16进制格式输入到大数
调用格式：N.Get(str,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
****************************************************************************************/
void CBigInt::Get(char str[],unsigned int system)
{
int len=strlen(str),k;
Mov(0);
for(int i=0;i<len;i++)
{
Mov(Mul(system));
if((str[i]>='0')&&(str[i]<='9'))k=str[i]-48;
else if((str[i]>='A')&&(str[i]<='F'))k=str[i]-55;
else if((str[i]>='a')&&(str[i]<='f'))k=str[i]-87;
else k=0;
Mov(Add(k));
}
}
/****************************************************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：N.Put(str,sys)
返回值：无，参数str被赋值为N的sys进制字符串
sys暂时只能为10或16
****************************************************************************************/
void CBigInt::Put(char str[],unsigned int system)
{
if((m_nLength==1)&&(m_ulValue[0]==0)){str="0";return;}
char t[]="0123456789ABCDEF";
int a;
char ch;
CBigInt X;
X.Mov(*this);
int i = 0;
while(X.m_ulValue[X.m_nLength-1]>0)
{
a=X.Mod(system);
ch=t[a];
str[i++] = ch;
X.Mov(X.Div(system));
}
str[i] = 0x00;
int len = strlen(str) - 1;
int half_len = strlen(str) / 2;
char tmp;
for (i = 0; i<half_len; i++)
{
tmp = str[i];
str[i] = str[len-i];
str[len-i] = tmp;
}
}
/****************************************************************************************
求不定方程ax-by=1的最小整数解
调用方式：N.Euc(A)
返回值：X,满足：NX mod A=1
****************************************************************************************/
CBigInt CBigInt::Euc(CBigInt& A)
{
CBigInt M,E,X,I,J;
int x,y;
M.Mov(A);
E.Mov(*this);
X.Mov(0);
Y.Mov(1);
x=y=1;
while((E.m_nLength!=1)||(E.m_ulValue[0]!=0))
{
I.Mov(M.Div(E));
J.Mov(M.Mod(E));
M.Mov(E);
E.Mov(J);
J.Mov(Y);
Y.Mov(Y.Mul(I));
if(x==y)
{
if(X.Cmp(Y)>=0)Y.Mov(X.Sub(Y));
else{Y.Mov(Y.Sub(X));y=0;}
}
else{Y.Mov(X.Add(Y));x=1-x;y=1-y;}
X.Mov(J);
}
if(x==0)X.Mov(A.Sub(X));
return X;
}
/****************************************************************************************
求乘方的模
调用方式：N.RsaTrans(A,B)
返回值：X=N^A MOD B
****************************************************************************************/
CBigInt CBigInt::RsaTrans(CBigInt& A,CBigInt& B)
{
CBigInt X,Y;
int i,k;
unsigned n;
unsigned long num;
k=A.m_nLength*32-32;
num=A.m_ulValue[A.m_nLength-1];
while(num){num=num>>1;k++;}
X.Mov(*this);
for(i=k-2;i>=0;i--)
{
Y.Mov(X.Mul(X.m_ulValue[X.m_nLength-1]));
Y.Mov(Y.Mod(B));
for(n=1;n<X.m_nLength;n++)
{
for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
Y.m_ulValue[0]=0;
Y.m_nLength++;
Y.Mov(Y.Add(X.Mul(X.m_ulValue[X.m_nLength-n-1])));
Y.Mov(Y.Mod(B));
}
X.Mov(Y);
if((A.m_ulValue[i>>5]>>(i&31))&1)
{
Y.Mov(Mul(X.m_ulValue[X.m_nLength-1]));
Y.Mov(Y.Mod(B));
for(n=1;n<X.m_nLength;n++)
{
for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
Y.m_ulValue[0]=0;
Y.m_nLength++;
Y.Mov(Y.Add(Mul(X.m_ulValue[X.m_nLength-n-1])));
Y.Mov(Y.Mod(B));
}
X.Mov(Y);
}
}
return X;
}
/****************************************************************************************
拉宾米勒算法测试素数
调用方式：N.Rab()
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
int CBigInt::Rab()
{
unsigned i,pass;
for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)return 0;}
CBigInt S,A,K;
K.Mov(*this);
K.m_ulValue[0]--;
for(i=0;i<5;i++)
{
pass=0;
A.Mov(rand()*rand());
S.Mov(K);
while((S.m_ulValue[0]&1)==0)
{
for(j=0;j<S.m_nLength;j++)
{
S.m_ulValue[j]=S.m_ulValue[j]>>1;
if(S.m_ulValue[j+1]&1)S.m_ulValue[j]=S.m_ulValue[j]|0x80000000;
}
if(S.m_ulValue[S.m_nLength-1]==0)S.m_nLength--;
I.Mov(A.RsaTrans(S,*this));
if(I.Cmp(K)==0){pass=1;break;}
}
if((I.m_nLength==1)&&(I.m_ulValue[0]==1))pass=1;
if(pass==0)return 0;
}
return 1;
}
/****************************************************************************************
产生随机素数
调用方法：N.GetPrime(bits)
返回值：N被赋值为一个bits位（0x100000000进制长度）的素数
****************************************************************************************/
void CBigInt::GetPrime(int bits)
{
unsigned i;
m_nLength=bits;
begin:
for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();
m_ulValue[0]=m_ulValue[0]|1;
for(i=m_nLength-1;i>0;i--)
{
m_ulValue[i]=m_ulValue[i]<<1;
if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++;
}
m_ulValue[0]=m_ulValue[0]<<1;
m_ulValue[0]++;
for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;}
CBigInt S,K;
K.Mov(*this);
K.m_ulValue[0]--;
for(i=0;i<5;i++)
{
A.Mov(rand()*rand());
S.Mov(K.Div(2));
I.Mov(A.RsaTrans(S,*this));
if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))goto begin;
}
}
int main()
{
int t;
int i,j;
CBigInt big_a,big_b,big_ans;
char ans[2005],a[1005],b[1005];
while (scanf("%d",&t) != EOF)
{
for (i = 0; i<t; i++)
{
if (i != 0)
printf("/n");
scanf("%s%s",a,b);
big_a.Get(a);
big_b.Get(b);
big_ans = big_a.Add(big_b);
big_ans.Put(ans);
printf("Case %d:/n%s + %s = %s/n",i+1,ans);
}
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |