我肝了一天半啊!!!!
终于把高精的模板搞出来了!!!
这个高精是直接用结构体封装的,然后可以很方便的直接声明高精变量,然后就可以像普通的高精一样使用了
现有如下两个版本
Code1:
不支持负数
1 struct HP { 2 int p[25555], len;//看题目开数组,最大就25555 3 bool flag; 4 HP () { 5 memset(p, 0, sizeof p); 6 len = 0, flag = false; 7 } 8 void in() { 9 char c = getchar(); 10 while (c < '0' || c > '9'){if (c == '-') flag ^= 1; c = getchar();} 11 while ('0' <= c && c <= '9') {p[++len] = c - '0'; c = getchar();} 12 for (int l = 1, r = len; l < r;) { 13 swap(p[l++], p[r--]); 14 } 15 } 16 void print() { 17 if (flag == true) printf("-"); 18 for (int i = len; i >= 1; i--) { 19 printf("%d", p[i]); 20 } 21 } 22 bool operator < (const HP &b) const {//高精之间比较 不支持负数 23 if(len != b.len) return len < b.len; 24 for (int i = len; i >= 1; i--) { 25 if(p[i] != b.p[i]) return p[i] < b.p[i]; 26 } 27 return false; 28 } 29 bool operator > (const HP &b) const { 30 if(len != b.len) return len > b.len; 31 for (int i = len; i >= 1; i--) { 32 if(p[i] != b.p[i]) return p[i] > b.p[i]; 33 } 34 return false; 35 } 36 bool operator <= (const HP &b) const { 37 if (len != b.len) return len < b.len; 38 for (int i = len; i >= 1; i--) { 39 if (p[i] != b.p[i]) return p[i] < b.p[i]; 40 } 41 return true; 42 } 43 bool operator >= (const HP &b) const { 44 if (len != b.len) return len > b.len; 45 for (int i = len; i >= 1; i--) { 46 if (p[i] != b.p[i]) return p[i] > b.p[i]; 47 } 48 return true; 49 } 50 bool operator == (const HP &b) const { 51 if (len != b.len) return false; 52 for (int i = len; i >= 1; i--) { 53 if (p[i] != b.p[i]) return false; 54 } 55 return true; 56 } 57 bool operator != (const HP &b) const { 58 if (len != b.len) return true; 59 for (int i = len; i >= 1; i--) { 60 if (p[i] != b.p[i]) return true; 61 } 62 return false; 63 } 64 HP operator + (const HP &b) const {//高精 + 高精 不支持负数 65 HP c; 66 c.len = max(len, b.len); 67 int re = 0; 68 for (int i = 1; i <= c.len; i++) { 69 re += p[i] + b.p[i]; 70 c.p[i] = re % 10; 71 re /= 10; 72 } 73 while (re) { 74 c.p[++c.len] = re % 10; 75 re /= 10; 76 } 77 return c; 78 } 79 HP operator - (const HP &B) const {//高精 - 高精 不支持负数相减 80 HP a = (*this), b = B, c; 81 if (a < b) {c.flag = true; swap(a, b);} 82 c.len = a.len; 83 int re = 0; 84 for (int i = 1; i <= c.len; i++) { 85 re += a.p[i] - b.p[i]; 86 if (re < 0) { 87 c.p[i] = re + 10; 88 re = -1; 89 } else { 90 c.p[i] = re; 91 re = 0; 92 } 93 } 94 while (c.len > 1 && c.p[c.len] == 0) c.len--; 95 return c; 96 } 97 HP operator * (const int &B) const {//高精 * 单精 不支持负数 98 if (B == 1) return (*this); 99 int b = B; 100 HP c; 101 c.len = len; 102 int re = 0; 103 for (int i = 1; i <= len; i++) { 104 re += p[i] * b; 105 c.p[i] = re % 10; 106 re /= 10; 107 } 108 while (re) { 109 c.p[++c.len] = re % 10; 110 re /= 10; 111 } 112 while (c.len > 1 && c.p[c.len] == 0) c.len--; 113 return c; 114 } 115 HP operator * (const HP &b) const {//高精 *高精 不支持负数 116 if (b.len == 1 && b.p[1] == 1) return (*this); 117 if (len == 1 && p[1] == 1) return b; 118 HP c; 119 c.len = len + b.len; 120 for (int i = 1; i <= len; i++) { 121 int re = 0; 122 for (int j = 1; j <= b.len; j++) { 123 c.p[i + j - 1] += p[i] * b.p[j] + re; 124 re = c.p[i + j - 1] / 10; 125 c.p[i + j - 1] %= 10; 126 } 127 c.p[i + b.len] = re; 128 } 129 while (c.p[c.len] > 0) c.len++; 130 while (c.len > 1 && c.p[c.len] == 0) c.len--; 131 return c; 132 } 133 HP operator / (const int &b) const {//高精 / 单精 不支持负数 134 if (b == 1) return (*this); 135 HP c; 136 c.len = len; 137 int re = 0; 138 for (int i = len; i >= 1; i--) { 139 re = re * 10 + p[i]; 140 c.p[i] = re / b; 141 re %= b; 142 } 143 while (c.len > 1 && c.p[c.len] == 0) c.len--; 144 return c; 145 } 146 bool div_cmp(const HP& b) {//用于优化高精 / 高精 147 if (len < b.len) return true; 148 for (int i = 0; i < b.len; i++) { 149 if (p[len - i] != b.p[b.len - i]) { 150 return p[len - i] < b.p[b.len - i]; 151 } 152 } 153 return false; 154 } 155 HP div_mul(int t) {//用于优化高精 / 高精 156 if (!t) return (*this); 157 HP c; 158 c.len = len + t; 159 for (int i = 1; i <= len; i++) { 160 c.p[i + t] = p[i]; 161 } 162 return c; 163 } 164 HP operator / (HP b) const {//高精 / 高精 不支持负数 165 if (b.len == 1 && b.p[1] == 1) return (*this); 166 if ((*this) < b) { 167 HP c; 168 c.len = 1, c.p[1] = 0; 169 return c; 170 } 171 HP a = (*this), c, tmp; 172 c.len = -1; 173 int l, t; 174 while (true) { 175 l = a.len - b.len - a.div_cmp(b); 176 if (l < 0) break; 177 tmp = b.div_mul(l); 178 t = 0; 179 while (tmp <= a) { 180 a = a - tmp; 181 t++; 182 } 183 if (c.len == -1 && t) { 184 c.len = l + 1; 185 } 186 c.p[l + 1] = t; 187 } 188 return c; 189 } 190 HP operator % (const int b) const {//高精 % 单精 191 HP d = (*this), c = (*this) / b; 192 c = c * b; 193 HP e = d - c; 194 return e; 195 } 196 HP operator % (const HP &b) const {//高精 % 高精 197 HP d = (*this), c = (*this) / b; 198 c = c * b; 199 HP e = d - c; 200 return e; 201 } 202 }; 203 HP Max(const HP &a, const HP &b) {//高精max 不支持负数 204 if (a.len > b.len) { 205 return a; 206 } else if (a.len < b.len) { 207 return b; 208 } 209 for (int i = a.len; i >= 1; i--) { 210 if (a.p[i] > b.p[i]) { 211 return a; 212 } else if (a.p[i] < b.p[i]) { 213 return b; 214 } 215 } 216 return a; 217 } 218 HP Min(const HP &a, const HP &b) {//高精min 不支持负数 219 if (a.len > b.len) { 220 return b; 221 } else if (a.len < b.len) { 222 return a; 223 } 224 for (int i = a.len; i >= 1; i--) { 225 if (a.p[i] < b.p[i]) { 226 return a; 227 } else if (a.p[i] > b.p[i]) { 228 return b; 229 } 230 } 231 return a; 232 }
Code2:
支持负数
1 struct HP { 2 int p[25555], len;//看题目开数组,最大就25555 3 bool flag; 4 HP () { 5 memset(p, 0, sizeof p); 6 len = 0, flag = false; 7 } 8 void in() { 9 char c = getchar(); 10 while (c < '0' || c > '9'){if (c == '-') flag ^= 1; c = getchar();} 11 while ('0' <= c && c <= '9') {p[++len] = c - '0'; c = getchar();} 12 for (int l = 1, r = len; l < r;) { 13 swap(p[l++], p[r--]); 14 } 15 } 16 void print() { 17 if (flag == true) printf("-"); 18 for (int i = len; i >= 1; i--) { 19 printf("%d", p[i]); 20 } 21 } 22 bool operator < (const HP &b) const {//高精之间的比较 支持负数 23 if (flag && !b.flag) return true; 24 if (!flag && b.flag) return false; 25 if (flag && b.flag) { 26 if(len != b.len) return len > b.len; 27 for (int i = len; i >= 1; i--) { 28 if(p[i] != b.p[i]) return p[i] > b.p[i]; 29 } 30 return false; 31 } else { 32 if(len != b.len) return len < b.len; 33 for (int i = len; i >= 1; i--) { 34 if(p[i] != b.p[i]) return p[i] < b.p[i]; 35 } 36 return false; 37 } 38 } 39 bool operator > (const HP &b) const { 40 if (flag && !b.flag) return false; 41 if (!flag && b.flag) return true; 42 if (flag && b.flag) { 43 if(len != b.len) return len < b.len; 44 for (int i = len; i >= 1; i--) { 45 if(p[i] != b.p[i]) return p[i] < b.p[i]; 46 } 47 return false; 48 } else { 49 if(len != b.len) return len > b.len; 50 for (int i = len; i >= 1; i--) { 51 if(p[i] != b.p[i]) return p[i] > b.p[i]; 52 } 53 return false; 54 } 55 } 56 bool operator <= (const HP &b) const { 57 if (flag && !b.flag) return true; 58 if (!flag && b.flag) return false; 59 if (flag && b.flag) { 60 if(len != b.len) return len > b.len; 61 for (int i = len; i >= 1; i--) { 62 if(p[i] != b.p[i]) return p[i] > b.p[i]; 63 } 64 return true; 65 } else { 66 if(len != b.len) return len < b.len; 67 for (int i = len; i >= 1; i--) { 68 if(p[i] != b.p[i]) return p[i] < b.p[i]; 69 } 70 return true; 71 } 72 } 73 bool operator >= (const HP &b) const { 74 if (flag && !b.flag) return false; 75 if (!flag && b.flag) return true; 76 if (flag && b.flag) { 77 if(len != b.len) return len < b.len; 78 for (int i = len; i >= 1; i--) { 79 if(p[i] != b.p[i]) return p[i] < b.p[i]; 80 } 81 return true; 82 } else { 83 if(len != b.len) return len > b.len; 84 for (int i = len; i >= 1; i--) { 85 if(p[i] != b.p[i]) return p[i] > b.p[i]; 86 } 87 return true; 88 } 89 } 90 bool operator == (const HP &b) const { 91 if (flag ^ b.flag) return false; 92 if (len != b.len) return false; 93 for (int i = len; i >= 1; i--) { 94 if (p[i] != b.p[i]) return false; 95 } 96 return true; 97 } 98 bool operator != (const HP &b) const { 99 if (flag ^ b.flag) return true; 100 if (len != b.len) return true; 101 for (int i = len; i >= 1; i--) { 102 if (p[i] != b.p[i]) return true; 103 } 104 return false; 105 } 106 HP operator + (const HP &B) const {//高精 + 高精 支持负数 107 HP b = B; 108 if (!flag && b.flag) { 109 b.flag = false; 110 return (*this) - b; 111 } 112 if (flag && !b.flag) { 113 HP a = (*this); 114 a.flag = false; 115 return b - a; 116 } 117 if (flag && B.flag) { 118 HP a = (*this), c; 119 a.flag = b.flag = false; 120 c = a + b; 121 c.flag = true; 122 return c; 123 } 124 HP c; 125 c.len = max(len, b.len); 126 int re = 0; 127 for (int i = 1; i <= c.len; i++) { 128 re += p[i] + b.p[i]; 129 c.p[i] = re % 10; 130 re /= 10; 131 } 132 while (re) { 133 c.p[++c.len] = re % 10; 134 re /= 10; 135 } 136 return c; 137 } 138 HP operator - (const HP &B) const {//高精 - 高精 支持负数 139 if (!flag && B.flag) { 140 HP b = B; 141 b.flag = false; 142 return (*this + b); 143 } 144 if (flag && !B.flag) { 145 HP a = (*this), c; 146 a.flag = false; 147 c = a + B; 148 c.flag = false; 149 return c; 150 } 151 if (flag && B.flag) { 152 HP a = (*this), b = B, c; 153 if (a < b) { 154 a.flag = b.flag = false; 155 c = a - b; 156 c.flag = true; 157 return c; 158 } else { 159 a.flag = b.flag = false; 160 c = b - a; 161 return c; 162 } 163 } 164 HP a = (*this), b = B, c; 165 if (a < b) {c.flag = true; swap(a, b);} 166 c.len = a.len; 167 int re = 0; 168 for (int i = 1; i <= c.len; i++) { 169 re += a.p[i] - b.p[i]; 170 if (re < 0) { 171 c.p[i] = re + 10; 172 re = -1; 173 } else { 174 c.p[i] = re; 175 re = 0; 176 } 177 } 178 while (c.len > 1 && c.p[c.len] == 0) c.len--; 179 return c; 180 } 181 HP operator * (const int &B) const {//高精 * 单精 支持负数 182 if (B == 1) return (*this); 183 int b = B; 184 HP c; 185 if (B < 0) { 186 b = -B; 187 c.flag = true; 188 } 189 if (flag) c.flag = true; 190 c.len = len; 191 int re = 0; 192 for (int i = 1; i <= len; i++) { 193 re += p[i] * b; 194 c.p[i] = re % 10; 195 re /= 10; 196 } 197 while (re) { 198 c.p[++c.len] = re % 10; 199 re /= 10; 200 } 201 while (c.len > 1 && c.p[c.len] == 0) c.len--; 202 return c; 203 } 204 HP operator * (const HP &b) const {//高精 * 高精 支持负数 205 if (b.len == 1 && b.p[1] == 1 && !b.flag) return (*this); 206 if (len == 1 && p[1] == 1 && !flag) return b; 207 HP c; 208 if (flag || b.flag) { 209 c.flag = flag ^ b.flag; 210 } 211 c.len = len + b.len; 212 for (int i = 1; i <= len; i++) { 213 int re = 0; 214 for (int j = 1; j <= b.len; j++) { 215 c.p[i + j - 1] += p[i] * b.p[j] + re; 216 re = c.p[i + j - 1] / 10; 217 c.p[i + j - 1] %= 10; 218 } 219 c.p[i + b.len] = re; 220 } 221 while (c.p[c.len] > 0) c.len++; 222 while (c.len > 1 && c.p[c.len] == 0) c.len--; 223 return c; 224 } 225 HP operator / (const int &b) const {//高精 / 单精 226 if (b == 1) return (*this); 227 HP c; 228 c.len = len; 229 int re = 0; 230 for (int i = len; i >= 1; i--) { 231 re = re * 10 + p[i]; 232 c.p[i] = re / b; 233 re %= b; 234 } 235 while (c.len > 1 && c.p[c.len] == 0) c.len--; 236 return c; 237 } 238 bool div_cmp(const HP& b) {//用于优化高精 / 高精 239 if (len < b.len) return true; 240 for (int i = 0; i < b.len; i++) { 241 if (p[len - i] != b.p[b.len - i]) { 242 return p[len - i] < b.p[b.len - i]; 243 } 244 } 245 return false; 246 } 247 HP div_mul(int t) {//用于优化高精 / 高精 248 if (!t) return (*this); 249 HP c; 250 c.len = len + t; 251 for (int i = 1; i <= len; i++) { 252 c.p[i + t] = p[i]; 253 } 254 return c; 255 } 256 HP operator / (HP b) const {//高精 / 高精 不支持负数 257 if (b.len == 1 && b.p[1] == 1) return (*this); 258 if ((*this) < b) { 259 HP c; 260 c.len = 1, c.p[1] = 0; 261 return c; 262 } 263 HP a = (*this), c, tmp; 264 c.len = -1; 265 int l, t; 266 while (true) { 267 l = a.len - b.len - a.div_cmp(b); 268 if (l < 0) break; 269 tmp = b.div_mul(l); 270 t = 0; 271 while (tmp <= a) { 272 a = a - tmp; 273 t++; 274 } 275 if (c.len == -1 && t) { 276 c.len = l + 1; 277 } 278 c.p[l + 1] = t; 279 } 280 return c; 281 } 282 HP operator % (const int b) const {//高精 % 单精 不支持负数 283 HP d = (*this), c = (*this) / b; 284 c = c * b; 285 HP e = d - c; 286 return e; 287 } 288 HP operator % (const HP &b) const {//高精 % 高精 不支持负数 289 HP d = (*this), c = (*this) / b; 290 c = c * b; 291 HP e = d - c; 292 return e; 293 } 294 }; 295 HP Max(const HP &a, const HP &b) {//高精max 不支持负数 296 if (a.len > b.len) { 297 return a; 298 } else if (a.len < b.len) { 299 return b; 300 } 301 for (int i = a.len; i >= 1; i--) { 302 if (a.p[i] > b.p[i]) { 303 return a; 304 } else if (a.p[i] < b.p[i]) { 305 return b; 306 } 307 } 308 return a; 309 } 310 HP Min(const HP &a, const HP &b) {//高精min 不支持负数 311 if (a.len > b.len) { 312 return b; 313 } else if (a.len < b.len) { 314 return a; 315 } 316 for (int i = a.len; i >= 1; i--) { 317 if (a.p[i] < b.p[i]) { 318 return a; 319 } else if (a.p[i] > b.p[i]) { 320 return b; 321 } 322 } 323 return a; 324 }
当然,我也不太敢保证完全无锅,但是我觉得差不多(逃