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

xuefu998

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

: P& c5 W7 B2 x0 |4 ~

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> . Z; L1 h' q! `$ U7 y. ]3 x# include <string> * g2 X+ U) C2 T9 j- l3 K( }$ Kusing namespace std;

typedef long long hugeint;

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

struct xnum 1 S6 s% E* k# L{ int Len; int Data[Capacity]; xnum() : Len(0) {} ; V9 t4 r1 u! I; I2 V xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } , b2 {8 R, i% R' ^3 c. D! I; x5 P9 D xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } 2 u6 L; d1 c& u! {5 u0 |! t2 n 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]; } ' `9 v: ^7 d$ M7 {1 a};

int compare(const xnum& A, const xnum& B) 3 V8 B! J6 @2 T" l S{ int I; 2 C* B/ Y4 @& u3 ?) k2 J% k if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; ! U& I. s& r# q% H1 W1 j for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); , v. E0 \ N k# p! |' h if (I < 0) return 0; return A[I] > B[I] ? 1 : -1; " }8 C$ R5 R$ w' ?7 C% t' j}

xnum operator+(const xnum& A, const xnum& B) 0 X2 ^7 o# Y9 C F0 y: R{ xnum R; int I; int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { $ _4 { g$ b/ S9 V, ~& d( N' u if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; + v" B& R5 F2 H5 f% i Carry /= Base; 9 Z4 d2 j! b/ O; g/ a( ?5 D" T& \ } 9 I [# n7 J T \ R.Len = I; ! E7 l1 w6 g, `! d# M return R; ) g8 s+ i! _) k( y}

xnum operator-(const xnum& A, const xnum& B) 7 W! h5 E6 x/ [2 h. g{ xnum R; ! J6 G, j& c7 t3 R( ]' e( n9 \6 L int Carry = 0; R.Len = A.Len; int I; ) K7 n6 ]- [* a; O for (I = 0; I < R.Len; I++) { 4 _7 {2 e. X, K6 z @' P) o R[I] = A[I] - Carry; ( h) K/ z7 _ T8 _$ S+ i- `# V if (I < B.Len) R[I] -= B[I]; : Q2 K: ^5 x* O$ d: F6 t if (R[I] < 0) Carry = 1, R[I] += Base; % U. v% E& s3 S else Carry = 0; 6 `7 M( W, i. H } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; ) C% ~( ^1 o/ T; D9 L return R; + o/ z2 O$ Q1 z6 `* p* m}

xnum operator*(const xnum& A, const int B) 5 h# }* a9 U/ E6 B' `' z{ ; B; [8 j; u N2 r. q! J& d+ [ int I; 3 ~- \3 t; b$ m& R ~6 p- q if (B == 0) return 0; 0 w$ @# P- o# g xnum R; + \! X+ S1 Y% a- |" ] hugeint Carry = 0; for (I = 0; I < A.Len || Carry > 0; I++) + A) p+ Q) P0 L7 h) E { . E6 f- g5 h9 f9 T3 x if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; Carry /= Base; ' y3 `( X5 b! \& f- K } R.Len = I; ! b; d$ s) ]# ~4 j return R; }

xnum operator*(const xnum& A, const xnum& B) { int I; if (B.Len == 0) return 0; xnum R; : E. b+ \( k7 w7 b! g3 y for (I = 0; I < A.Len; I++) { hugeint Carry = 0; ; d2 {: _. H Y( }$ v4 K3 y3 h for (int J = 0; J < B.Len || Carry > 0; J++) { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 1 \# |; c& q. L7 R" _" a2 f if (I + J < R.Len) Carry += R[I + J]; / L' K/ T( |# E4 d# X5 u( o: B% H if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; P/ f- `4 p# G$ w) J Carry /= Base; : y* \2 R. Z& } } } / Y* N: Q! x0 W$ G6 _' R) b8 Y" t return R; 5 U+ x" G; K: l& k4 i: k- X) D}

xnum operator/(const xnum& A, const int B) ; d) Q! {3 d7 h" |{ % r2 n( k, z* s! \ xnum R; - O Y' \$ I8 D. ]: }) Q+ W0 z5 @7 H4 L int I; 5 y. ?$ m- M8 A( h7 U- u# d hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) / O0 P A) b y( E$ l) q { ! ]6 n+ ?% v. L3 [; Y& J C = C * Base + A[I]; ) z( T& E& ?6 s R[I] = C / B; ; p a+ ^* W3 S; E C %= B; ; u% ]* B5 h7 N7 n8 \ } R.Len = A.Len; 1 ~$ A% L1 k/ Q while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; ' R7 ]- |7 {1 }}

xnum operator/(const xnum& A, const xnum& B) { int I; xnum R, Carry = 0; int Left, Right, Mid; # N0 I8 R- A$ K5 v- v for (I = A.Len - 1; I >= 0; I--) / Y5 O7 d0 T4 J. i { Carry = Carry * Base + A[I]; , b! I5 u2 k3 P1 j+ T( f6 [ Left = 0; , o% |4 L2 b0 c Right = Base - 1; while (Left < Right) { & e' \+ _# \( A" o Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } 1 f, X. X3 L4 u- ]9 _8 N R[I] = Left; " B% y( ]' V6 h1 Y, p4 A Carry = Carry - B * Left; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; } & |. N2 W( }; @( G( X/ vxnum operator%(const xnum& A, const xnum& B) 3 U& `8 W4 P, g{ ' Z2 l! X! _* { int I; xnum R, Carry = 0; ' T6 N$ d N2 {9 n int Left, Right, Mid; # B/ l+ ~6 c3 u3 M A9 U, p for (I = A.Len - 1; I >= 0; I--) ) l2 {% S4 d3 s+ C { Carry = Carry * Base + A[I]; Left = 0; 7 g. I, I9 s; Y) J0 v Right = Base - 1; . B0 W0 s( ]2 F' F) M* H- K while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; 3 V2 \: I: }# C% n; j! Y else Right = Mid - 1; } : L7 K" R& t0 l" h5 h P3 U R[I] = Left; Carry = Carry - B * Left; # w% h. F) A1 _ } R.Len = A.Len; / S" W- B# V5 H* q while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; : j/ X8 b# B( A return Carry; }

istream& operator>>(istream& In, xnum& V) 8 @; y! |% b% @, C) R( p2 N{ char Ch; ! N6 s9 ~. V# e! O0 j/ B5 m for (V = 0; In >> Ch;) { ) z/ _5 ]- ~, O' S! T; g" k2 G V = V * 10 + (Ch - '0'); 3 \& l c: @. [9 c if (cin.peek() <= ' ') break; } " Q2 G/ H& o9 `+ b return In; }

ostream& operator<<(ostream& Out, const xnum& V) { ) g* M( ^" R( v; Z, |5 x int I; 3 ? R+ {( E' W3 y- q" `0 U, A! i Out << (V.Len == 0 ? 0 : V[V.Len - 1]); ! K" P8 @3 `0 s/ P7 r( y7 O for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; ( @* _$ U2 M' c return Out; }

wangjiaqi49

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

cshdzxjtu

强！