谁有超长整数运算的好算法？

xuefu998

谁有超长整数运算的好算法？

* g' i. I( R' d! f" U) I; ~

现在CPU还是64位的，量长整数不过int64（2^64），超过这个数的整数怎么办，如1000！等，请各位有心人指点迷津。

[em08][em08][em08]

aftermath

高精度，用一个线性表保存一个大整数，具体说，将大整数写成p进制数，线性表的每一项存p进制其中一位。

参考下面代码

#include <iostream> + v: D% {; _( l3 i9 t#include <memory> $ u8 l" M, M6 u; w( V0 u1 q9 m# include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; const int Capacity = 200;

struct xnum ( R9 Z9 ]+ ]9 m; d{ int Len; 9 S# @; H% ~0 `: l int Data[Capacity]; 1 S' q& S5 H$ E) o xnum() : Len(0) {} xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } 9 T, C0 u* l l8 t xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } , E8 j4 z& h: O7 z xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } };

7 Y0 y) B+ M6 n$ lint compare(const xnum& A, const xnum& B) * J% S) w/ M A8 c& ^{ int I; ( g" w4 G$ S0 l# V if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); ; o; V9 p% w# Z% ^; n, w if (I < 0) return 0; return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) + E8 _' h7 C# l" D: p: s{ ~( v1 @; Y6 W. ^" X# d) w# ]# | xnum R; * J4 c: {6 m5 r3 k- P* S. r2 Z1 J int I; % d- w! Z$ ^+ t0 I int Carry = 0; `4 C1 d& x$ @7 } for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { 0 v$ s% J# ]3 I- U( g( I# P U if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; - s* I; Q, l: Y) s- M+ Y$ L Carry /= Base; : e) i8 ^# ^5 G4 _- o! M } . I+ K5 p- M% S* l2 E" e R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) { % w* m" T, H1 _8 w xnum R; int Carry = 0; 4 e) P" |( N8 M3 ~4 M9 M R.Len = A.Len; 0 {0 p1 ^% t. P" B* W0 \; C int I; 7 I! T0 l, Q. k+ q for (I = 0; I < R.Len; I++) ; A% q4 h& V+ S; ` { " X6 |2 c e N' a" e5 \ R[I] = A[I] - Carry; & H; ~, Q( y7 M. i9 q! z if (I < B.Len) R[I] -= B[I]; . m2 C. u2 W8 H8 ^ if (R[I] < 0) Carry = 1, R[I] += Base; 1 e9 b; c& [* ]2 y" n else Carry = 0; } , n. N) V" H g4 k+ |; s7 Z while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator*(const xnum& A, const int B) { 6 U7 e* K: I7 m) i6 e9 P int I; # y2 n' Q' N6 h% z2 g* b2 l+ ^5 J if (B == 0) return 0; # A! c+ G1 Q8 m; D- l+ ~6 x xnum R; ( v2 q+ Q. j( c f4 K/ w" U4 } hugeint Carry = 0; ( a {6 K$ @$ r4 R+ w for (I = 0; I < A.Len || Carry > 0; I++) { 2 c. ]3 _; n. j- h9 N9 e if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; 0 l( a, A6 P5 D2 d Carry /= Base; } 9 j! }4 c4 y% n: X; k. l- L" x R.Len = I; return R; / z" u R6 D6 U3 ?7 `}

xnum operator*(const xnum& A, const xnum& B) 6 h7 ~$ g+ Y: z7 }: E2 c3 s{ int I; if (B.Len == 0) return 0; 3 w p- X8 Y4 |4 X) \' j xnum R; * [* _% W3 g0 Y7 I5 g for (I = 0; I < A.Len; I++) { hugeint Carry = 0; 7 p1 G, b7 J0 f) V for (int J = 0; J < B.Len || Carry > 0; J++) 7 T( V7 j5 r" a$ o8 A7 h# v: N { $ ]7 [% R: X8 c) T' y2 `9 s if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 5 q8 t) h# q9 g' |. q if (I + J < R.Len) Carry += R[I + J]; : D; J5 X7 }7 G1 r+ z1 _ if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; ) f9 }3 ~, T7 I4 z Carry /= Base; } ; K/ [6 N& r* y( l' n) j) [ } ( ?& ^ ?6 Y( S, P9 m return R; 6 Q. W+ ?" b" }" t8 t}

xnum operator/(const xnum& A, const int B) # u7 }2 E* w J: H* v{ xnum R; int I; ) B# e' Z' T& l7 a" `( J1 \ hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) ) [3 h. q3 f0 `0 ^6 M { 1 L y( Z3 y; Q) j4 z: X C = C * Base + A[I]; # [/ D$ u; p& n+ @ h R[I] = C / B; : a3 `( t) E9 P1 h) }5 R- ^' | C %= B; . k, f/ X. n4 _$ Y# v. g1 U } 3 p i ]8 r; f& q8 ]' B$ ]" }( S' a R.Len = A.Len; & D, ^! ~3 L/ r W while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 1 ]# Z( o9 K# p+ ~4 E1 F) l# Y$ z+ ` return R; $ O! C8 _ J3 [( n5 u. @6 a" Y}

xnum operator/(const xnum& A, const xnum& B) { 2 A, i' z8 @ g/ o int I; xnum R, Carry = 0; / Z% c' ~' H* l. h' B' m; h6 |* ? int Left, Right, Mid; 2 w1 S8 |3 s6 P& n# U; f for (I = A.Len - 1; I >= 0; I--) 0 v8 W& R/ { ]/ L e { Carry = Carry * Base + A[I]; Left = 0; Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; , Z) H( }4 @" d6 B if (compare(B * Mid, Carry) <= 0) Left = Mid; % n" K) K0 C6 A: h! t @ else Right = Mid - 1; } + ]9 i5 g/ v# j1 W/ N/ x R[I] = Left; 4 C' S4 V8 S/ s. ^ Carry = Carry - B * Left; 9 I9 F, V" h; Q# B/ { } 7 S! r' k! b: M5 j R.Len = A.Len; 6 B7 m) r, A( N/ z2 H while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; } 8 [9 q4 J: t; D1 axnum operator%(const xnum& A, const xnum& B) 1 l/ P) e7 |, g3 @{ int I; " _$ j4 N) f2 n: E8 z+ D xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) - k; P. n- X+ U) i9 ? { % T( n# R; s2 q- ^1 l Carry = Carry * Base + A[I]; Left = 0; 9 b: R) d$ X' _4 {, F) |- O Right = Base - 1; while (Left < Right) { 4 D0 ] j# g% K/ A" B/ ]- I) Z( K Mid = (Left + Right + 1) / 2; ! u, O3 W2 Z( |5 m: p2 M% _) O: @: \ if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; ! w6 H p% w1 o/ d; [2 y: I1 k } R[I] = Left; Carry = Carry - B * Left; + F- n+ s- z, _# e6 w( }8 l } 2 f. F1 r( h) v* D! o R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; & f4 D. y' l* G1 ~. M; H8 e$ f return Carry; }

istream& operator>>(istream& In, xnum& V) * G2 N3 M Y/ F{ char Ch; for (V = 0; In >> Ch;) { . K' Z& X& \- F, M V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; } " r' K. E$ \6 @: i* x return In; }

ostream& operator<<(ostream& Out, const xnum& V) { $ I" ?9 Y" s+ M& k" X# K$ I int I; Out << (V.Len == 0 ? 0 : V[V.Len - 1]); for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; ; C+ X7 x& i! L6 I return Out; 1 u$ K# v8 }; J; f. n) i6 i/ I}

wangjiaqi49

神人也，外星人！！太牛了

cshdzxjtu

强！