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

xuefu998

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

5 Q4 k4 |' Y: U) q8 y1 u

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> 9 U. m, O7 x* v& Y; h9 r# include <string> using namespace std;

typedef long long hugeint;

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

struct xnum % i$ M+ c w. z7 o, Q{ 1 c/ N+ y1 m; ?! J b& F$ A int Len; int Data[Capacity]; * f8 M. }5 t% l) O xnum() : Len(0) {} 5 B3 W1 U/ R4 {3 A5 M. ~ xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } int& operator[](int Index) { return Data[Index]; } 3 T* v$ }( W' ~, W4 v int operator[](int Index) const { return Data[Index]; } };

int compare(const xnum& A, const xnum& B) ! s. N' Y W1 C b* j* y{ $ \/ p4 g, ]) Z: K int I; ! }) A' u/ |- p# G. \% M# x 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; return A[I] > B[I] ? 1 : -1; # n1 C7 V. C" U* e8 r}

xnum operator+(const xnum& A, const xnum& B) ) e e6 W4 k' Y{ 9 C# ?$ ?1 d4 W. ]# S xnum R; 6 I5 F7 O& E- D+ S$ M0 a/ y int I; : S( h3 \5 j, W$ Z& D2 y/ v, q5 ] int Carry = 0; 8 z4 ~8 F: e) g8 M P5 d% i for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) 6 _( s2 N5 n! `5 Y* w { { * X8 S) a2 ^3 f( C+ O6 @5 ? if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; ( t0 b8 h2 f9 l2 m- w' C R[I] = Carry % Base; . M0 q! |: `. m Carry /= Base; } R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) 3 I. X, _6 g2 W{ xnum R; int Carry = 0; 1 w3 d4 K4 ?3 v6 q/ T; @0 k- A R.Len = A.Len; 8 m2 Z+ V3 b* i2 M int I; for (I = 0; I < R.Len; I++) { R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; # n H4 ]; E# m if (R[I] < 0) Carry = 1, R[I] += Base; ) b% `' I% u9 o" K else Carry = 0; } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; , v, _1 U. S# I3 Q. e" }9 c}

xnum operator*(const xnum& A, const int B) { * }$ r) E e/ n; {/ M int I; 6 Z" Z1 v) h9 m1 q; S5 t: \ if (B == 0) return 0; xnum R; hugeint Carry = 0; ( n2 }! D& s G5 r3 c# B- j for (I = 0; I < A.Len || Carry > 0; I++) { if (I < A.Len) Carry += hugeint(A[I]) * B; / |3 E- A( L! n R[I] = Carry % Base; 2 C2 e. g; S7 H! s Carry /= Base; } + v8 P% T/ k% v u: W! g R.Len = I; 6 u! e/ b2 N: E return R; ! {1 x' t0 y0 a5 ]}

xnum operator*(const xnum& A, const xnum& B) { . |, {" b/ J F E( O! i4 S int I; - K5 u: I5 J; |. \+ _ if (B.Len == 0) return 0; xnum R; 2 N/ t e b' A0 N for (I = 0; I < A.Len; I++) { hugeint Carry = 0; 6 U$ J' {3 E6 u- ?, T$ R6 E for (int J = 0; J < B.Len || Carry > 0; J++) 7 v) d( v$ M, { R" @& Q u { $ q( B) `0 x8 c if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; & }: m" M, K3 Z% V. D2 [ if (I + J >= R.Len) R[R.Len++] = Carry % Base; / D; o. ?* T9 i* u. q/ ?0 u4 L, m else R[I + J] = Carry % Base; Carry /= Base; } # Z# p& V" f* W8 P/ d: l( V+ m; o } return R; }

xnum operator/(const xnum& A, const int B) 7 a8 u& Y1 @* m1 P/ K @- P/ V4 [0 x{ 5 ?. b- o% S; F) a xnum R; 5 I3 s9 K, h8 q. r' z$ n3 M int I; hugeint C = 0; [. r) \& b- j for (I = A.Len - 1; I >= 0; I--) { * |, k1 w) G) }3 I2 m C = C * Base + A[I]; ' Y$ o3 O/ O+ T3 _ q) h R[I] = C / B; , }1 o K: f N! Y( N2 d C %= B; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; / U( } e6 ?: _! V4 S0 | return R; }

xnum operator/(const xnum& A, const xnum& B) { int I; / A. g, t2 C3 b6 o/ ]' l xnum R, Carry = 0; int Left, Right, Mid; + f! U) _! Q B+ l for (I = A.Len - 1; I >= 0; I--) + e" ~& v6 I- l. v( W3 e { 2 [ P* d: N+ P1 [, N0 n Carry = Carry * Base + A[I]; Left = 0; 8 W3 A# P1 M8 ~" `; G2 k1 w! Q! s Right = Base - 1; 2 X- c! h' o; Q# J4 m while (Left < Right) & j [$ }( m! b: Z. ?3 B. l& ` { Mid = (Left + Right + 1) / 2; " N1 d% G$ W, ~9 B% U" M9 n& h if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } ! I/ F, f1 r+ a z! m$ o2 E7 f6 b$ j R[I] = Left; Carry = Carry - B * Left; ; L9 b; d6 q1 {! g, E# E" e+ w: { } , W. n- p1 u+ U1 n R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; . |% s' D8 E ~8 a( L% G" O5 M- R3 v return R; } " {+ D Q( X9 Y% v: v$ Nxnum operator%(const xnum& A, const xnum& B) 2 F7 t4 i; f$ F9 `8 Y+ ]6 H; k{ int I; xnum R, Carry = 0; 4 H, Y4 R, f* m. ~9 b1 I int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { 6 s* I$ C, K' ^# R1 S Carry = Carry * Base + A[I]; 0 [# I7 J/ [; D$ {" `9 S$ s- O% X$ F Left = 0; Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; " _) } L" P- y8 w1 N( v else Right = Mid - 1; } 2 b1 z3 I y' E) G R[I] = Left; Carry = Carry - B * Left; * n& X5 G7 v! W3 E# e \3 Y: N } 6 a+ T1 P$ \4 W; z7 S8 F0 I' G' y8 r R.Len = A.Len; . `8 m: \3 s$ o! m/ v4 D8 } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; ' t7 U ?& x6 K/ q9 J4 l3 I, t6 d return Carry; ; V- [6 u* [# r' h; ^9 v}

istream& operator>>(istream& In, xnum& V) , n; _: a- y; G{ char Ch; 7 T+ x$ q# z3 z {: S for (V = 0; In >> Ch;) % g8 Q0 ?+ o% _9 N { V = V * 10 + (Ch - '0'); , e, F: D8 U3 w- ~ if (cin.peek() <= ' ') break; # g0 g7 m: |4 p0 }4 x/ b) I } return In; " T- a* B: o e) I% d: ~}

ostream& operator<<(ostream& Out, const xnum& V) { : q. p4 z) [6 |, e4 K6 H int I; 6 E$ @) H7 l: J2 t 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; : { Q3 ~; \& B- h' [% t return Out; }

wangjiaqi49

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

cshdzxjtu

强！