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

xuefu998

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

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> 2 o! N$ j7 }+ F# d1 v- [# include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; 3 R2 b/ p) r" y, y0 dconst int Capacity = 200;

struct xnum 5 t) l2 o( j9 _: C, `{ * P+ s2 q& p" w int Len; int Data[Capacity]; xnum() : Len(0) {} xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } 9 t. l6 c8 X; Q* ` P6 t xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } 8 ?! c9 a( x7 }7 i: }) r9 U xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } 5 K; c9 p+ B# n \! S int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } 6 J _1 W4 f8 g$ j/ P" P};

int compare(const xnum& A, const xnum& B) { 6 X" ]) s$ h& t7 j 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--); if (I < 0) return 0; 9 T$ d, F0 F% u return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) { , y) M1 W- U: Q2 g6 C" e xnum R; 5 I2 l, `/ B0 U! V& P' m int I; int Carry = 0; " [8 ^0 o% H* `* G' r: M6 ] for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { * ]/ `, K) U: ~, k& k if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; . U) m( `6 E6 Z: D+ I R[I] = Carry % Base; Carry /= Base; } 0 Q: @9 b6 [( @9 g* g R.Len = I; return R; + s0 A) Z- `5 a+ ] `}

xnum operator-(const xnum& A, const xnum& B) , W4 ~; t2 e$ M. Q{ xnum R; int Carry = 0; ; g7 ?) a! }$ O, c" h0 F% o3 [; \ R.Len = A.Len; 0 H* |, |4 y/ s, `5 w4 H7 q ` [+ z int I; for (I = 0; I < R.Len; I++) , S. ~% V" z/ G" {5 T+ C/ h2 ` { & d# k( ?% ?4 W) s' k; c* w2 @) l R[I] = A[I] - Carry; , }) W: n- J7 a8 c4 J7 J4 Q if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; } 8 ?9 y" R2 y2 t while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; / l; M& G3 j! r}

xnum operator*(const xnum& A, const int B) { , q( i7 ^% P: J8 ?% k7 m. z int I; ) D, h' \; g8 g6 t if (B == 0) return 0; xnum R; hugeint Carry = 0; for (I = 0; I < A.Len || Carry > 0; I++) 9 y+ ?0 x5 p' ]; d# u { if (I < A.Len) Carry += hugeint(A[I]) * B; - h$ Z1 d1 j8 c9 D* W R[I] = Carry % Base; $ @2 C/ b S* X. X& | Carry /= Base; ( M* { B3 O0 h2 h- x; N } # {3 S+ [+ H6 J4 @* H( m5 f9 _ R.Len = I; return R; }

xnum operator*(const xnum& A, const xnum& B) { int I; ; w% ]8 U, i: K if (B.Len == 0) return 0; d( H: w0 M$ `* i7 l$ G xnum R; 2 W V% V& J$ P1 Q) J for (I = 0; I < A.Len; I++) { & t+ W7 [5 r( f& f. h hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) { + j* _ B: L2 C. U7 J if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 0 }! p# J) A/ t0 z) S if (I + J < R.Len) Carry += R[I + J]; 7 S& A( h8 C$ u) {( B j* P if (I + J >= R.Len) R[R.Len++] = Carry % Base; ' Y2 d: E5 [5 Q' _# m: K( Y else R[I + J] = Carry % Base; Carry /= Base; 9 O+ Y) M: t2 T5 D } 1 j/ N$ }! J( R. ^: q( H } 0 Z) c: \: n ^- d return R; }

xnum operator/(const xnum& A, const int B) { xnum R; int I; hugeint C = 0; ! C7 V, ~' Y$ T# |3 Q5 a9 x [ for (I = A.Len - 1; I >= 0; I--) 7 r& Z) l, d0 G/ q0 L { C = C * Base + A[I]; C2 u1 \/ X6 @" Z R[I] = C / B; % `( ^: i3 v* g2 e N C %= B; E R4 Z( y& N( D } : e* i% S; q. m& m h R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; 8 v% E! n5 K8 T+ e& c}

xnum operator/(const xnum& A, const xnum& B) 8 y9 ]6 Q/ }8 h6 I# m5 C" j4 ~+ [{ int I; xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) , h' ^% Q, k0 m7 N& D! o { 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; . _5 X9 S6 q! m: k1 h- M. K } R[I] = Left; " P' E1 W1 c* U' b. _5 S, _ Carry = Carry - B * Left; T6 d4 ?+ s( }* A, r! z3 g, k } + J \5 i, |6 {6 P% C% m' Z R.Len = A.Len; 4 k, z v0 [) b- t. R while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; } xnum operator%(const xnum& A, const xnum& B) { int I; ) ?2 U8 Y9 X+ t W E xnum R, Carry = 0; ) u5 v: z5 t0 q& C9 I- M int Left, Right, Mid; ( s; ~# a" g2 o2 U% q9 b) ]" s for (I = A.Len - 1; I >= 0; I--) 3 z7 Q% w: a* S; v: v { Carry = Carry * Base + A[I]; 7 m5 }0 \4 E) G \9 u Left = 0; Right = Base - 1; while (Left < Right) . a% P) D# D n# F6 q& }5 D { ) h% v! x' ]" a5 S Mid = (Left + Right + 1) / 2; 8 U' Z4 d$ V9 Y if (compare(B * Mid, Carry) <= 0) Left = Mid; / w* W4 C& g1 L( I/ ?; O else Right = Mid - 1; ; I0 V G6 c. x* Y g/ R) J } $ p- j# @8 U7 c2 u, w, g# e" A R[I] = Left; Carry = Carry - B * Left; 2 I3 N! ]# B6 j' h } R.Len = A.Len; X* ~$ N! y8 g$ \5 M/ R% B$ N' ~ while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; }

istream& operator>>(istream& In, xnum& V) 6 A1 l6 H y$ t/ C{ char Ch; $ o O# P2 x5 r5 L. m for (V = 0; In >> Ch;) { 0 H8 c' M# }2 W7 t* E* k V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; & D5 Y% c# \0 W+ Z6 ^. y% g3 ~, `5 W } return In; - ?; [" G9 {9 u& x/ j* J0 m}

ostream& operator<<(ostream& Out, const xnum& V) 8 p4 G# O9 d' m0 O% e1 `{ 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; 6 M# ], T8 ?8 \& A return Out; }

wangjiaqi49

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

cshdzxjtu

强！