前言
本文的所有代码用C++实现，若在代码段里发现未定义的行为，请到最后的完整代码里寻找该行为含义。若有错误敬请在评论区指正。谢谢您的阅读。
出发点
普通高精度每一位存一个数字，可是对于一个int型的存储空间，可存的最大数值为2147483647，只存一个数字是极大的空间浪费。因此，为了在节约空间的同时减少时间复杂度，我们尽量在一个空间中多存几位数字。对于乘法，两数之积的位数最大可达到两数的位数和，所以一个空间中存4位数字，可以保证不会溢出。
准备
一个数有以下几个信息：长度、每一位数的数字、符号，因此我们定义Integer类的成员如下：
1 1 const int Max_Integer_Length=6000;//类外 2 2 private: 3 3 int digit[Max_Integer_Length],count; 4 4 short signum;
操作
1.输入输出
类似于普通高精度，我们用一个char数组来辅助输入。先将所有数据输入到char数组当中，再把char数组每四位切割一次，倒序存到digit数组当中。（倒序是为了运算的时候方便处理）对于符号位，我们不妨使用一个start变量记录是否为负，如果是，循环的时候对char数组则从第1位而非第0位开始。较麻烦的是对于char数组和digit数组位置对应公式的推导，因为一个是顺序，另一个是逆序。
类似地，对于输出，先判断是否为负，如果是就输出'-'，然后对digit数组倒序输出，注意要用零补齐4位。
1 inline Integer::Integer(const char *target) 2 { 3 memset(digit,0,sizeof(digit)); 4 int start=0,len=strlen(target); 5 if(target[0]=='-'&&(target[1]!='0'||len!=2)) 6 { 7 signum=-1; 8 ++start; 9 } 10 else if(target[0]!='0'||len!=1) 11 signum=1; 12 else 13 signum=0; 14 count=(len-start-1)/4; 15 for(int i=start,sum=0;i<len;++i) 16 { 17 sum=sum*10+target[i]-'0'; 18 if(!((len-i-1)%4)) 19 { 20 digit[count-(i-start)/4]=sum; 21 sum=0; 22 } 23 } 24 while(count>0&&!digit[count]) 25 --count; 26 } 27 inline std::istream& operator >>(std::istream &Cin,Integer &target) 28 { 29 scanf("%s",char_array_temp); 30 target=Integer(char_array_temp); 31 return Cin; 32 }
1 inline std::ostream& operator <<(std::ostream &Cout,const Integer &target) 2 { 3 if(target.signum==-1) 4 printf("-"); 5 printf("%d",target.digit[target.count]); 6 for(int i=target.count-1;i>-1;--i) 7 printf("%04d",target.digit[i]); 8 return Cout; 9 }
2.大小比较
与普通高精度类似，先比符号，再比大小，最后逆序比较每一位。写好'＜'和'=='后，为了节省代码量，可以用符号之间的关系来写其它运算符。
1 inline bool operator <(const Integer &target1,const Integer &target2) 2 { 3 if(target1.signum!=target2.signum) 4 return target1.signum<target2.signum; 5 if(target1.signum==-1) 6 return target2.absolute_value()<target1.absolute_value(); 7 if(target1.count!=target2.count) 8 return target1.count<target2.count; 9 for(int i=target1.count;i>-1;--i) 10 if(target1.digit[i]!=target2.digit[i]) 11 return target1.digit[i]<target2.digit[i]; 12 return false; 13 } 14 inline bool operator >(const Integer &target1,const Integer &target2) 15 { 16 return !(target1<target2)&&!(target1==target2); 17 } 18 inline bool operator ==(const Integer &target1,const Integer &target2) 19 { 20 if(target1.signum!=target2.signum||target1.count!=target2.count) 21 return false; 22 for(int i=target1.count;i>-1;--i) 23 if(target1.digit[i]!=target2.digit[i]) 24 return false; 25 return true; 26 } 27 inline bool operator <=(const Integer &target1,const Integer &target2) 28 { 29 return target1<target2||target1==target2; 30 } 31 inline bool operator >=(const Integer &target1,const Integer &target2) 32 { 33 return !(target1<target2); 34 } 35 inline bool operator !=(const Integer &target1,const Integer &target2) 36 { 37 return !(target1==target2); 38 }
3.算术运算
对于加减乘法，和普通高精度相同，我们按照竖式计算的方式模拟。
加法从低位起，两个运算数x，y的对应位分别相加，然后满10000进1。时间复杂度为O(max(x.count，y.count))。
减法从低位起，被减数x的每一位分别减去减数y的对应位，如果为负则向下一位借1当10000。时间复杂度为O(max(x.count，y.count))。
乘法从低位起，第一个因数x的每一位与第二个因数y的每一位分别相乘，第i位与第j位所得的结果累加到结果的第i+j位，然后满10000进1。时间复杂度为O(x.count*y.count)。
对于符号，加减法在异号时互相转换调用，而乘法则只需要按同号为正，异号为负的方法得出符号。
注意减法和乘法可能产生的前导零需要删除。
1 inline Integer Integer::absolute_value(void)const 2 { 3 if(!count&&!signum) 4 return *this; 5 else 6 { 7 Integer result=*this; 8 result.signum=1; 9 return result; 10 } 11 } 12 inline Integer Integer::opposite_number(void)const 13 { 14 Integer result=*this; 15 result.signum*=-1; 16 return result; 17 }
1 inline Integer operator +(const Integer &target1,const Integer &target2) 2 { 3 if(target1.signum!=target2.signum) 4 if(!target1.signum||!target2.signum) 5 return target1.signum?target1:target2; 6 else return target1.signum<target2.signum?target2-target1.absolute_value():target1-target2.absolute_value(); 7 Integer result; 8 result.count=target1.count<target2.count?target2.count:target1.count; 9 result.signum=target1.signum; 10 for(int i=0;i<=result.count;++i) 11 { 12 result.digit[i]+=target1.digit[i]+target2.digit[i]; 13 result.digit[i+1]=result.digit[i]/10000; 14 result.digit[i]%=10000; 15 } 16 if(result.digit[result.count+1]) 17 ++result.count; 18 return result; 19 } 20 inline Integer operator -(const Integer &target1,const Integer &target2) 21 { 22 if(target1.signum!=target2.signum) 23 if(!target1.signum||!target2.signum) 24 return target1.signum?target1:target2.opposite_number(); 25 else return target1.signum<target2.signum?(target1.absolute_value()+target2).opposite_number():target1+target2.absolute_value(); 26 if(target1<target2) 27 return (target2-target1).opposite_number(); 28 Integer result; 29 if(target1==target2) 30 return result; 31 result.count=target1.count; 32 result.signum=1; 33 for(int i=0;i<=result.count;++i) 34 { 35 result.digit[i]+=target1.digit[i]-target2.digit[i]; 36 if(result.digit[i]<0) 37 { 38 --result.digit[i+1]; 39 result.digit[i]+=10000; 40 } 41 } 42 while(result.count>0&&!result.digit[result.count]) 43 --result.count; 44 return result; 45 } 46 inline Integer operator *(const Integer &target1,const Integer &target2) 47 { 48 Integer result; 49 if(!target1.signum&&!target2.signum) 50 return result; 51 result.signum=target1.signum*target2.signum; 52 result.count=target1.count+target2.count+1; 53 for(int i=0;i<=target1.count;++i) 54 for(int j=0;j<=target2.count;++j) 55 { 56 result.digit[i+j]+=target1.digit[i]*target2.digit[j]; 57 result.digit[i+j+1]+=result.digit[i+j]/10000; 58 result.digit[i+j]%=10000; 59 } 60 while(result.count>0&&!result.digit[result.count]) 61 --result.count; 62 return result; 63 }
对于除法，首先我们模拟竖式计算，首先将除数y的末位与被除数x的首位对齐（这个过程相当于扩大了除数），然后将除数的末位将不断向被除数当前位的下一位移动（相当于将除数除以10000），直到到达其末位，并在每一次移动和对齐后在被除数上尽量多地在减去除数当前的相对大小，同时将减去的次数累加到结果的被除数当前位的对应位。
那么对于这里的尽量多地减去除数这一操作，我们写普通高精度使用的是试除法，也就是不断地判断，如果被除数大于除数就减。
1 inline Integer operator /(Integer target1,Integer target2) 2 { 3 Integer result,temp; 4 if(!target1.signum||target1.absolute_value()<target2.absolute_value()) 5 return result; 6 if(!target2.signum) 7 throw std::logic_error("divide by zero!"); 8 result.signum=target1.signum*target2.signum; 9 result.count=target1.count-target2.count+1; 10 target1=target1.absolute_value(); 11 for(int i=result.count;i>-1;--i) 12 { 13 temp.zero(); 14 for(int j=0;j<=target2.count;++j) 15 temp.digit[i+j]=target2.digit[j]; 16 temp.count=target2.count+i; 17 temp.signum=1; 18 while(target1>=temp) 19 { 20 ++result.digit[i]; 21 target1-=temp; 22 } 23 } 24 while(result.count>0&&!result.digit[result.count]) 25 --result.count; 26 return result; 27 }
可是我们计算一下这样做的最坏时间复杂度：试除每次最多可能进行9999次，也就是每一位要执行9999次减法，总时间复杂度将达到9999*O(x.count*y.count)，显然对于数据稍微苛刻的题就会TLE。关键是而构造这样的数据极为简单，x的每一位都是9999，y为1，这就是最坏情况。未压位之前，每一位最多试除9次，4位就是36次，远远低于9999次。
因此，我们不能直接试除。对于“尽量多”这一个字眼，我们可以联想到一个时间复杂度较优的算法——二分答案。于是，我们对于每一次试除，在左边界为0，右边界为9999的区间内进行二分（边界可以进行优化），找到尽量多的减法次数。由于这里的乘法的另一个因数为不超过9999的整数，存储到Integer里只有一位，乘法复杂度仅为O(y.count)，总时间复杂度为O(x.count*y.count)*k，其中k=log210000≈13。即使未压位前使用了二分试除，4位的复杂度也有4*log210≈12，由于减法未压位的常数更大，甚至压位会更快。
但是，在洛谷 P2005 A/B Problem II中，这样的二分还是会TLE。我们再对常数进行优化，在进行二分之前判断此时的被除数和除数的大小，如果被除数更小就不再进行二分，这样就避免了一次O(y.count)*k的二分。
1 inline Integer operator /(const Integer &target1,const Integer &target2) 2 { 3 Integer result,temp,now; 4 if(!target1.signum||target1.absolute_value()<target2.absolute_value()) 5 return result; 6 if(!target2.signum) 7 throw std::logic_error("divide by zero!"); 8 result.signum=target1.signum*target2.signum; 9 result.count=target1.count; 10 now.signum=1; 11 for(int i=result.count;i>-1;--i) 12 { 13 for(int j=now.count;j>-1;--j) 14 now.digit[j+1]=now.digit[j]; 15 now.digit[0]=target1.digit[i]; 16 if(now.digit[now.count+1]) 17 ++now.count; 18 now.signum=1; 19 if(now<target2) 20 continue; 21 int left=0,right=9999; 22 while(left<right) 23 { 24 int mid=(left+right)/2; 25 if(target2*Integer(mid)<=now) 26 left=mid+1; 27 else 28 right=mid; 29 } 30 result.digit[i]=left-1; 31 now-=Integer(left-1)*target2; 32 } 33 while(result.count>0&&!result.digit[result.count]) 34 --result.count; 35 return result; 36 }
取余可以直接通过除法和乘法来实现。对于被除数x和除数y，我们有x%y=x-x/y*y。
1 inline Integer operator %(const Integer &target1,const Integer &target2) 2 { 3 return target1-target1/target2*target2; 4 }
优点
相比起普通的高精度而言，压位高精度将空间节约到了原来的四分之一，同时因为压位位数减少，加减和比较操作时间也几乎缩短到了原来的四分之一，乘法甚至几乎缩短到了原来的十六分之一。
完整代码
1 #ifndef _INTEGER_HPP_ 2 #define _INTEGER_HPP_ 3 4 #include<cstdio> 5 #include<cstring> 6 #include<iostream> 7 #include<stdexcept> 8 9 namespace PsephurusGladius 10 { 11 namespace integer 12 { 13 const int Max_Integer_Length=6000; 14 char char_array_temp[Max_Integer_Length]; 15 class Integer 16 { 17 private: 18 int digit[Max_Integer_Length],count; 19 short signum; 20 public: 21 Integer(void); 22 Integer(const Integer &target); 23 Integer(const long long &target); 24 Integer(const char *target); 25 operator char*(void); 26 void zero(void); 27 friend std::istream& operator >>(std::istream &Cin,Integer &target); 28 friend std::ostream& operator <<(std::ostream &Cout,const Integer &target); 29 Integer absolute_value(void)const; 30 Integer opposite_number(void)const; 31 Integer operator -(void)const; 32 friend bool operator <(const Integer &target1,const Integer &target2); 33 friend bool operator >(const Integer &target1,const Integer &target2); 34 friend bool operator <=(const Integer &target1,const Integer &target2); 35 friend bool operator >=(const Integer &target1,const Integer &target2); 36 friend bool operator ==(const Integer &target1,const Integer &target2); 37 friend bool operator !=(const Integer &target1,const Integer &target2); 38 friend Integer operator +(const Integer &target1,const Integer &target2); 39 friend Integer operator -(const Integer &target1,const Integer &target2); 40 friend Integer operator *(const Integer &target1,const Integer &target2); 41 friend Integer operator /(const Integer &target1,const Integer &target2); 42 friend Integer operator %(const Integer &target1,const Integer &target2); 43 Integer& operator ++(void); 44 Integer operator ++(int); 45 Integer& operator --(void); 46 Integer operator --(int); 47 Integer operator +=(const Integer &target); 48 Integer operator -=(const Integer &target); 49 Integer operator *=(const Integer &target); 50 Integer operator /=(const Integer &target); 51 Integer operator %=(const Integer &target); 52 }; 53 inline Integer::Integer(void):count(0),signum(0) 54 { 55 memset(digit,0,sizeof(digit)); 56 } 57 inline Integer::Integer(const Integer &target):count(target.count),signum(target.signum) 58 { 59 memcpy(digit,target.digit,sizeof(digit)); 60 } 61 inline Integer::Integer(const long long &target) 62 { 63 memset(digit,0,sizeof(digit)); 64 signum=target<0?-1:(target>0?1:0); 65 count=-1; 66 long long temp=target; 67 do 68 { 69 digit[++count]=temp%10000; 70 temp/=10000; 71 } 72 while(temp); 73 } 74 inline Integer::Integer(const char *target) 75 { 76 memset(digit,0,sizeof(digit)); 77 int start=0,len=strlen(target); 78 if(target[0]=='-'&&(target[1]!='0'||len!=2)) 79 { 80 signum=-1; 81 ++start; 82 } 83 else if(target[0]!='0'||len!=1) 84 signum=1; 85 else 86 signum=0; 87 count=(len-start-1)/4; 88 for(int i=start,sum=0;i<len;++i) 89 { 90 sum=sum*10+target[i]-'0'; 91 if(!((len-i-1)%4)) 92 { 93 digit[count-(i-start)/4]=sum; 94 sum=0; 95 } 96 } 97 while(count>0&&!digit[count]) 98 --count; 99 } 100 inline Integer::operator char*(void) 101 { 102 memset(char_array_temp,0,sizeof(char_array_temp)); 103 for(int i=count,len=0;i>-1;--i) 104 { 105 if(i==count) 106 { 107 len+=sprintf(char_array_temp+len,"%d",digit[i]); 108 continue; 109 } 110 len+=sprintf(char_array_temp+len,"%04d",digit[i]); 111 } 112 return char_array_temp; 113 } 114 inline void Integer::zero(void) 115 { 116 memset(digit,0,sizeof(digit)); 117 count=signum=0; 118 } 119 inline std::istream& operator >>(std::istream &Cin,Integer &target) 120 { 121 scanf("%s",char_array_temp); 122 target=Integer(char_array_temp); 123 return Cin; 124 } 125 inline std::ostream& operator <<(std::ostream &Cout,const Integer &target) 126 { 127 if(target.signum==-1) 128 printf("-"); 129 printf("%d",target.digit[target.count]); 130 for(int i=target.count-1;i>-1;--i) 131 printf("%04d",target.digit[i]); 132 return Cout; 133 } 134 inline Integer Integer::absolute_value(void)const 135 { 136 if(!count&&!signum) 137 return *this; 138 else 139 { 140 Integer result=*this; 141 result.signum=1; 142 return result; 143 } 144 } 145 inline Integer Integer::opposite_number(void)const 146 { 147 Integer result=*this; 148 result.signum*=-1; 149 return result; 150 } 151 Integer Integer::operator -(void)const 152 { 153 return opposite_number(); 154 } 155 inline bool operator <(const Integer &target1,const Integer &target2) 156 { 157 if(target1.signum!=target2.signum) 158 return target1.signum<target2.signum; 159 if(target1.signum==-1) 160 return target2.absolute_value()<target1.absolute_value(); 161 if(target1.count!=target2.count) 162 return target1.count<target2.count; 163 for(int i=target1.count;i>-1;--i) 164 if(target1.digit[i]!=target2.digit[i]) 165 return target1.digit[i]<target2.digit[i]; 166 return false; 167 } 168 inline bool operator >(const Integer &target1,const Integer &target2) 169 { 170 return !(target1<target2)&&!(target1==target2); 171 } 172 inline bool operator ==(const Integer &target1,const Integer &target2) 173 { 174 if(target1.signum!=target2.signum||target1.count!=target2.count) 175 return false; 176 for(int i=target1.count;i>-1;--i) 177 if(target1.digit[i]!=target2.digit[i]) 178 return false; 179 return true; 180 } 181 inline bool operator <=(const Integer &target1,const Integer &target2) 182 { 183 return target1<target2||target1==target2; 184 } 185 inline bool operator >=(const Integer &target1,const Integer &target2) 186 { 187 return !(target1<target2); 188 } 189 inline bool operator !=(const Integer &target1,const Integer &target2) 190 { 191 return !(target1==target2); 192 } 193 inline Integer operator +(const Integer &target1,const Integer &target2) 194 { 195 if(target1.signum!=target2.signum) 196 if(!target1.signum||!target2.signum) 197 return target1.signum?target1:target2; 198 else return target1.signum<target2.signum?target2-target1.absolute_value():target1-target2.absolute_value(); 199 Integer result; 200 result.count=target1.count<target2.count?target2.count:target1.count; 201 result.signum=target1.signum; 202 for(int i=0;i<=result.count;++i) 203 { 204 result.digit[i]+=target1.digit[i]+target2.digit[i]; 205 result.digit[i+1]=result.digit[i]/10000; 206 result.digit[i]%=10000; 207 } 208 if(result.digit[result.count+1]) 209 ++result.count; 210 return result; 211 } 212 inline Integer operator -(const Integer &target1,const Integer &target2) 213 { 214 if(target1.signum!=target2.signum) 215 if(!target1.signum||!target2.signum) 216 return target1.signum?target1:target2.opposite_number(); 217 else return target1.signum<target2.signum?(target1.absolute_value()+target2).opposite_number():target1+target2.absolute_value(); 218 if(target1<target2) 219 return (target2-target1).opposite_number(); 220 Integer result; 221 if(target1==target2) 222 return result; 223 result.count=target1.count; 224 result.signum=1; 225 for(int i=0;i<=result.count;++i) 226 { 227 result.digit[i]+=target1.digit[i]-target2.digit[i]; 228 if(result.digit[i]<0) 229 { 230 --result.digit[i+1]; 231 result.digit[i]+=10000; 232 } 233 } 234 while(result.count>0&&!result.digit[result.count]) 235 --result.count; 236 return result; 237 } 238 inline Integer operator *(const Integer &target1,const Integer &target2) 239 { 240 Integer result; 241 if(!target1.signum&&!target2.signum) 242 return result; 243 result.signum=target1.signum*target2.signum; 244 result.count=target1.count+target2.count+1; 245 for(int i=0;i<=target1.count;++i) 246 for(int j=0;j<=target2.count;++j) 247 { 248 result.digit[i+j]+=target1.digit[i]*target2.digit[j]; 249 result.digit[i+j+1]+=result.digit[i+j]/10000; 250 result.digit[i+j]%=10000; 251 } 252 while(result.count>0&&!result.digit[result.count]) 253 --result.count; 254 return result; 255 } 256 inline Integer operator /(const Integer &target1,const Integer &target2) 257 { 258 Integer result,temp,now; 259 if(!target1.signum||target1.absolute_value()<target2.absolute_value()) 260 return result; 261 if(!target2.signum) 262 throw std::logic_error("divide by zero!"); 263 result.signum=target1.signum*target2.signum; 264 result.count=target1.count; 265 now.signum=1; 266 for(int i=result.count;i>-1;--i) 267 { 268 for(int j=now.count;j>-1;--j) 269 now.digit[j+1]=now.digit[j]; 270 now.digit[0]=target1.digit[i]; 271 if(now.digit[now.count+1]) 272 ++now.count; 273 now.signum=1; 274 if(now<target2) 275 continue; 276 int left=0,right=9999; 277 while(left<right) 278 { 279 int mid=(left+right)/2; 280 if(target2*Integer(mid)<=now) 281 left=mid+1; 282 else 283 right=mid; 284 } 285 result.digit[i]=left-1; 286 now-=Integer(left-1)*target2; 287 } 288 while(result.count>0&&!result.digit[result.count]) 289 --result.count; 290 return result; 291 } 292 inline Integer operator %(const Integer &target1,const Integer &target2) 293 { 294 return target1-target1/target2*target2; 295 } 296 inline Integer& Integer::operator ++(void) 297 { 298 return *this=*this+Integer(1LL); 299 } 300 inline Integer Integer::operator ++(int) 301 { 302 Integer result=*this; 303 ++*this; 304 return result; 305 } 306 inline Integer& Integer::operator --(void) 307 { 308 return *this=*this-Integer(1LL); 309 } 310 inline Integer Integer::operator --(int) 311 { 312 Integer result=*this; 313 --*this; 314 return result; 315 } 316 inline Integer Integer::operator +=(const Integer &target) 317 { 318 return *this=*this+target; 319 } 320 inline Integer Integer::operator -=(const Integer &target) 321 { 322 return *this=*this-target; 323 } 324 inline Integer Integer::operator *=(const Integer &target) 325 { 326 return *this=*this*target; 327 } 328 inline Integer Integer::operator /=(const Integer &target) 329 { 330 return *this=*this/target; 331 } 332 inline Integer Integer::operator %=(const Integer &target) 333 { 334 return *this=*this%target; 335 } 336 } 337 } 338 339 #endif
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
