C++ 大数模板
浏览数：24 /
时间：2015年06月08日
适合我这种不会java的SB
没有大数%大数
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <string.h> 5 using namespace std; 6 /* 7 * 完全大数模板 8 * 输出cin>>a 9 * 输出a.print(); 10 * 注意这个输入不能自动去掉前导0的，可以先读入到char数组，去掉前导0，再用构造函数。 11 */ 12 #define MAXN 9999 13 #define MAXSIZE 1010 14 #define DLEN 4 15 class BigNum 16 { 17 private: 18 int a[5000]; //可以控制大数的位数 19 int len; 20 public: 21 BigNum(){len=1;memset(a,0,sizeof(a));} //构造函数 22 BigNum(const int); //将一个int类型的变量转化成大数 23 BigNum(const char*); //将一个字符串类型的变量转化为大数 24 BigNum(const BigNum &); //拷贝构造函数 25 BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算 26 friend istream& operator>>(istream&,BigNum&); //重载输入运算符 27 friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符 28 BigNum operator+(const BigNum &)const; //重载加法运算符，两个大数之间的相加运算 29 BigNum operator-(const BigNum &)const; //重载减法运算符，两个大数之间的相减运算 30 BigNum operator*(const BigNum &)const; //重载乘法运算符，两个大数之间的相乘运算 31 BigNum operator/(const int &)const; //重载除法运算符，大数对一个整数进行相除运算 32 BigNum operator^(const int &)const; //大数的n次方运算 33 34 int operator%(const int &)const; //大数对一个int类型的变量进行取模运算 35 BigNum operator% (const BigNum &)const; 36 bool operator>(const BigNum &T)const; //大数和另一个大数的大小比较 37 bool operator>(const int &t)const; //大数和一个int类型的变量的大小比较 38 void print(); //输出大数 39 }; 40 41 BigNum::BigNum(const int b) //将一个int类型的变量转化为大数 42 { 43 int c,d=b; 44 len=0; 45 memset(a,0,sizeof(a)); 46 while(d>MAXN) 47 { 48 c=d-(d/(MAXN+1))*(MAXN+1); 49 d=d/(MAXN+1); 50 a[len++]=c; 51 } 52 a[len++]=d; 53 } 54 55 BigNum::BigNum(const char *s) //将一个字符串类型的变量转化为大数 56 { 57 int t,k,index,L,i; 58 memset(a,0,sizeof(a)); 59 L=strlen(s); 60 len=L/DLEN; 61 if(L%DLEN)len++; 62 index=0; 63 for(i=L-1;i>=0;i-=DLEN) 64 { 65 t=0; 66 k=i-DLEN+1; 67 if(k<0)k=0; 68 for(int j=k;j<=i;j++) 69 t=t*10+s[j]-‘0‘; 70 a[index++]=t; 71 } 72 } 73 74 BigNum::BigNum(const BigNum &T):len(T.len) //拷贝构造函数 75 { 76 int i; 77 memset(a,0,sizeof(a)); 78 for(i=0;i<len;i++) 79 a[i]=T.a[i]; 80 } 81 BigNum & BigNum::operator=(const BigNum &n) //重载赋值运算符，大数之间赋值运算 82 { 83 int i; 84 len=n.len; 85 memset(a,0,sizeof(a)); 86 for(i=0;i<len;i++) 87 a[i]=n.a[i]; 88 return *this; 89 } 90 91 istream& operator>>(istream &in,BigNum &b) 92 { 93 char ch[MAXSIZE*4]; 94 int i=-1; 95 in>>ch; 96 int L=strlen(ch); 97 int count=0,sum=0; 98 for(i=L-1;i>=0;) 99 { 100 sum=0; 101 int t=1; 102 for(int j=0;j<4&&i>=0;j++,i--,t*=10) 103 { 104 sum+=(ch[i]-‘0‘)*t; 105 } 106 b.a[count]=sum; 107 count++; 108 } 109 b.len=count++; 110 return in; 111 } 112 113 ostream& operator<<(ostream& out,BigNum& b) //重载输出运算符 114 { 115 int i; 116 cout<<b.a[b.len-1]; 117 for(i=b.len-2;i>=0;i--) 118 { 119 printf("%04d",b.a[i]); 120 } 121 return out; 122 } 123 124 BigNum BigNum::operator+(const BigNum &T)const //两个大数之间的相加运算 125 { 126 BigNum t(*this); 127 int i,big; 128 big=T.len>len?T.len:len; 129 for(i=0;i<big;i++) 130 { 131 t.a[i]+=T.a[i]; 132 if(t.a[i]>MAXN) 133 { 134 t.a[i+1]++; 135 t.a[i]-=MAXN+1; 136 } 137 } 138 if(t.a[big]!=0) 139 t.len=big+1; 140 else t.len=big; 141 return t; 142 } 143 144 BigNum BigNum::operator-(const BigNum &T)const //两个大数之间的相减运算 145 { 146 int i,j,big; 147 bool flag; 148 BigNum t1,t2; 149 if(*this>T) 150 { 151 t1=*this; 152 t2=T; 153 flag=0; 154 } 155 else 156 { 157 t1=T; 158 t2=*this; 159 flag=1; 160 } 161 big=t1.len; 162 for(i=0;i<big;i++) 163 { 164 if(t1.a[i]<t2.a[i]) 165 { 166 j=i+1; 167 while(t1.a[j]==0) 168 j++; 169 t1.a[j--]--; 170 while(j>i) 171 t1.a[j--]+=MAXN; 172 t1.a[i]+=MAXN+1-t2.a[i]; 173 } 174 else t1.a[i]-=t2.a[i]; 175 } 176 t1.len=big; 177 while(t1.a[len-1]==0 && t1.len>1) 178 { 179 t1.len--; 180 big--; 181 } 182 if(flag) 183 t1.a[big-1]=0-t1.a[big-1]; 184 return t1; 185 } 186 187 BigNum BigNum::operator*(const BigNum &T)const //两个大数之间的相乘 188 { 189 BigNum ret; 190 int i,j,up; 191 int temp,temp1; 192 for(i=0;i<len;i++) 193 { 194 up=0; 195 for(j=0;j<T.len;j++) 196 { 197 temp=a[i]*T.a[j]+ret.a[i+j]+up; 198 if(temp>MAXN) 199 { 200 temp1=temp-temp/(MAXN+1)*(MAXN+1); 201 up=temp/(MAXN+1); 202 ret.a[i+j]=temp1; 203 } 204 else 205 { 206 up=0; 207 ret.a[i+j]=temp; 208 } 209 } 210 if(up!=0) 211 ret.a[i+j]=up; 212 } 213 ret.len=i+j; 214 while(ret.a[ret.len-1]==0 && ret.len>1)ret.len--; 215 return ret; 216 } 217 218 BigNum BigNum::operator/(const int &b)const //大数对一个整数进行相除运算 219 { 220 BigNum ret; 221 int i,down=0; 222 for(i=len-1;i>=0;i--) 223 { 224 ret.a[i]=(a[i]+down*(MAXN+1))/b; 225 down=a[i]+down*(MAXN+1)-ret.a[i]*b; 226 } 227 228 ret.len=len; 229 while(ret.a[ret.len-1]==0 && ret.len>1) 230 ret.len--; 231 return ret; 232 } 233 234 int BigNum::operator%(const int &b)const //大数对一个 int类型的变量进行取模 235 { 236 int i,d=0; 237 for(i=len-1;i>=0;i--) 238 d=((d*(MAXN+1))%b+a[i])%b; 239 return d; 240 } 241 BigNum BigNum:: operator% (const BigNum &b) const 242 { 243 BigNum tmp=(*this); 244 while (tmp-b>0) 245 { 246 tmp=tmp-b; 247 } 248 if (!((tmp%b)>0)) tmp=tmp-b; 249 return tmp; 250 } 251 252 BigNum BigNum::operator^(const int &n)const //大数的n次方运算 253 { 254 BigNum t,ret(1); 255 int i; 256 if(n<0)exit(-1); 257 if(n==0)return 1; 258 if(n==1)return *this; 259 int m=n; 260 while(m>1) 261 { 262 t=*this; 263 for(i=1;(i<<1)<=m;i<<=1) 264 t=t*t; 265 m-=i; 266 ret=ret*t; 267 if(m==1)ret=ret*(*this); 268 } 269 return ret; 270 } 271 272 bool BigNum::operator>(const BigNum &T)const //大数和另一个大数的大小比较 273 { 274 int ln; 275 if(len>T.len)return true; 276 else if(len==T.len) 277 { 278 ln=len-1; 279 while(a[ln]==T.a[ln]&&ln>=0) 280 ln--; 281 if(ln>=0 && a[ln]>T.a[ln]) 282 return true; 283 else 284 return false; 285 } 286 else 287 return false; 288 } 289 bool BigNum::operator>(const int &t)const //大数和一个int类型的变量的大小比较 290 { 291 BigNum b(t); 292 return *this>b; 293 } 294 void BigNum::print() //输出大数 295 { 296 int i; 297 printf("%d",a[len-1]); 298 for(i=len-2;i>=0;i--) 299 printf("%04d",a[i]); 300 printf("\n"); 301 } 302 BigNum f[1130];//卡特兰数 303 BigNum _Pow(BigNum &a,BigNum &b,BigNum &c) 304 { 305 BigNum d,e,f; 306 d=a,e=b,f=1; 307 while (e>0) 308 { 309 if (e%2) f=f*d%c; 310 e=e/2; 311 d=d*d%c; 312 } 313 return f; 314 } 315 316 bool RabinMill(BigNum &n) 317 { 318 BigNum b,m,j,v,i; 319 m=n-1; 320 j=0; 321 while (m%2>0) 322 { 323 j=j+1; 324 m=m/2; 325 } 326 327 } 328 int main() 329 { 330 /* f[0]=1; 331 for(int i=1;i<=435;i++) 332 f[i]=f[i-1]*(4*i-2)/(i+1);//卡特兰数递推式 333 int n; 334 while(scanf("%d",&n)==1) 335 { 336 if(n==-1)break; 337 f[n].print(); 338 } 339 */ 340 BigNum a,b,c; 341 cin>>a>>b; 342 c=a%b; 343 c.print(); 344 345 return 0; 346 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
