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

xuefu998

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

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> # include <string> using namespace std;

typedef long long hugeint;

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

struct xnum ( S" o1 M; D# g{ + M- U! D$ d% `/ ?) J8 i int Len; int Data[Capacity]; 0 ?% y9 d5 I) t# L' U+ ?% Z6 K xnum() : Len(0) {} ( z& X/ Y2 C" H- G# y xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } : C/ z3 o5 o0 i8 Z xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } & ?% C5 O* O/ E2 P- K: h1 P- o xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } int& operator[](int Index) { return Data[Index]; } b2 ]4 @0 T$ z: L! _+ O int operator[](int Index) const { return Data[Index]; } };

6 m, ~- y) E: h0 xint compare(const xnum& A, const xnum& B) 4 L5 s7 F% Q- d{ 3 o6 F% M" o' @ A int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); ) a/ T2 M' N$ K. A5 q. G. K2 E if (I < 0) return 0; " I# |9 t( d7 t return A[I] > B[I] ? 1 : -1; 3 n+ r, G( m9 `. ?}

xnum operator+(const xnum& A, const xnum& B) { , m ~+ p8 ~4 t/ }. U" z; w% U7 Z! D xnum R; int I; / K, R) T' P' f. Z( Z' I, c% G int Carry = 0; ; b2 p* y2 o: J C; c2 S+ u+ y" X for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) ( t) s9 L4 r e( V { / a" L' B. t/ L if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; 5 P6 p+ g6 b T! W D$ b R[I] = Carry % Base; " Z8 J" m ]) y2 ^, L( s0 ~! f Carry /= Base; } R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) { ' Q$ @; j7 D' O x& A5 O, N6 b xnum R; 6 B& }7 ]1 y/ g& a int Carry = 0; R.Len = A.Len; 9 T3 O* d1 f, g; o2 x int I; . g0 A3 h* P" J& C for (I = 0; I < R.Len; I++) { 2 F% N- D8 k$ M: C, D @% a# O8 r R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; 8 M4 G, d* D% {" ]- B1 C/ [ d if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; } 3 R0 ]+ a7 \4 Z% e while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; ' R. v7 N5 z0 a% e9 g3 u- R return R; 0 T9 q5 _, `' j# T}

xnum operator*(const xnum& A, const int B) { int I; if (B == 0) return 0; ! C8 }) Y. v& ` xnum R; ; F2 q d8 C4 `' Z' Z0 @3 k hugeint Carry = 0; ! } y% K6 U6 ^" N, f; Y0 o for (I = 0; I < A.Len || Carry > 0; I++) * P) \) M+ _% f3 A3 ?! V { 7 A! W h+ r3 Z2 ` if (I < A.Len) Carry += hugeint(A[I]) * B; ; |+ _: {4 X2 P, N$ L) f R[I] = Carry % Base; & M" J, m H4 T' F" o# \% F) ? Carry /= Base; } R.Len = I; / i0 Y% ~: V8 Q! C, I. p7 u/ T return R; $ C4 q% C# M9 N}

xnum operator*(const xnum& A, const xnum& B) 6 J' P6 E; X# O2 [( H+ t2 O{ int I; if (B.Len == 0) return 0; xnum R; for (I = 0; I < A.Len; I++) ) j5 w0 R ^0 |6 U { / A/ H( s3 R2 z hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; 5 F8 I5 H& c$ Y if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; / ?% P+ P7 _, H: U Carry /= Base; & n+ z/ B, W9 t. s } } return R; . H/ H! o! T8 f$ t6 S}

xnum operator/(const xnum& A, const int B) * D; g$ |9 ~: [5 u* \{ % C* n( \1 p+ D& ~9 ] xnum R; Z4 ?% C& R) p. y6 u9 W8 U int I; hugeint C = 0; , H2 @4 m6 u* i for (I = A.Len - 1; I >= 0; I--) { * H+ j; X4 F, X4 d0 {9 O( F. f! s9 m C = C * Base + A[I]; R[I] = C / B; * Q: g) E) b" }% p C %= B; - J, B! E- z: p6 m4 \2 s: Q: E- R } R.Len = A.Len; , f- i2 u* b1 Y- {% L& H while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; $ B6 i' d/ _- q$ I. [+ G. N return R; 6 J, c+ C/ m5 I}

xnum operator/(const xnum& A, const xnum& B) { int I; xnum R, Carry = 0; . [1 F# z9 M: z int Left, Right, Mid; ; K& M5 a. b" |' Z" l% r for (I = A.Len - 1; I >= 0; I--) { ! M. p7 H7 ]% y8 Q# X; p Carry = Carry * Base + A[I]; Left = 0; ) q0 h6 z4 x1 f0 M% | Right = Base - 1; / {0 m6 o+ u, Y, z1 a while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } R[I] = Left; Carry = Carry - B * Left; : O/ g# u* D5 U4 B } ! ]: ~( F6 e) ]% ?. A# v, a R.Len = A.Len; , ^8 |# O/ O1 X- Y7 [ while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; # Y4 W% m$ M: l3 } return R; } C3 E" Z, Y5 k- W3 X, F- c8 j1 Z [xnum operator%(const xnum& A, const xnum& B) { " h) q( Z1 K/ Q/ k int I; " C! o1 C* W( f" t ~0 Q xnum R, Carry = 0; int Left, Right, Mid; 1 P' M0 M! a# F# v for (I = A.Len - 1; I >= 0; I--) 7 J- [7 |. x3 q2 b$ Q5 H% S { Carry = Carry * Base + A[I]; Left = 0; Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } 1 w! ~5 s( D. b8 z$ ] R[I] = Left; - ]0 i+ X/ a! u' N7 l2 P9 ?+ s Carry = Carry - B * Left; } 0 D( x# q: g- G) z7 k8 \, z$ x R.Len = A.Len; - t$ i* k- O" X! |3 O while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; 1 v0 `# z% }: o1 E6 Z* `* y8 C* J}

istream& operator>>(istream& In, xnum& V) { 7 J4 U0 M' P% f5 Y( S8 D char Ch; for (V = 0; In >> Ch;) 2 W: V0 a* s7 z+ D2 E9 V { V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; } return In; }

ostream& operator<<(ostream& Out, const xnum& V) { 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; % f3 r5 `" T6 e return Out; / Q2 C% Y x( n7 E# E* Y} 5 Z! d: j- B4 S9 A3 H; [( n

wangjiaqi49

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

cshdzxjtu

强！