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

xuefu998

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

* Z3 ^2 P5 I, B/ X, q

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> $ Q0 s3 f8 B2 J1 w/ X: V# include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; - i' T& }4 z: Mconst int Capacity = 200;

struct xnum { 1 V; g, G) e$ \ int Len; int Data[Capacity]; 3 |# k8 r0 ~" Z* J# P& a }5 G xnum() : Len(0) {} 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; } 9 Q) f1 }, s2 C' `+ r( { Q8 k4 b 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]; } };

int compare(const xnum& A, const xnum& B) 5 A3 @/ U, u: w6 v; X1 {, p! a" Q. X( _{ int I; & O' h5 U* w7 T1 E( 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; return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) { ! y: J8 R+ a9 e" d/ f xnum R; 9 G6 X' Q: O* H; h( O3 v' B/ i; m int I; . W0 Z8 }- R% q2 X" w int Carry = 0; 2 `: R! C8 X" f0 _' n1 Z% ?& e for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) ) C) F5 F- ^) d' v { 5 s6 q& z, u6 V K2 A if (I < A.Len) Carry += A[I]; " T* L T/ J3 e2 E7 |' { if (I < B.Len) Carry += B[I]; w$ s0 }3 ^; J$ v | R[I] = Carry % Base; Carry /= Base; $ |2 ~" `) q( @ } R.Len = I; # b, I# _5 z" O& P return R; 6 `+ z( A! ^& p* ^; b' q}

xnum operator-(const xnum& A, const xnum& B) , F% r& N( j0 {{ & O+ U, \ c3 S9 `5 q xnum R; int Carry = 0; ) ~% z5 a" v+ r% u% g R.Len = A.Len; int I; ! [. m9 l {4 b4 X. s7 e* x for (I = 0; I < R.Len; I++) 3 W) j0 {7 [+ k( i. j { 1 [- c% H& E- C/ \6 ] R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; * ]6 [% n- U) Y0 P7 I, F' r+ h else Carry = 0; } " T( x7 ?$ v n4 l while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; 2 ^% k! ]% _$ P; ^: x3 q}

xnum operator*(const xnum& A, const int B) & v$ M) s5 Q1 U( Y& r" X8 l{ 0 A. {# I" f, B+ r. A( \ int I; if (B == 0) return 0; xnum R; & y3 l: x. C/ J. n' ^8 I hugeint Carry = 0; 3 ^' ~1 t: ~5 m8 i* R for (I = 0; I < A.Len || Carry > 0; I++) " I6 L% i$ w, E* i( k3 d. Y& { { if (I < A.Len) Carry += hugeint(A[I]) * B; ' B5 T, x0 G" W% w R[I] = Carry % Base; " p# F( }1 @% z: h! C6 A8 ~ Carry /= Base; $ b$ ^$ p/ A4 G9 B } R.Len = I; 1 B0 R5 j2 O2 B) {; O5 u. z# @2 N2 O return R; }

xnum operator*(const xnum& A, const xnum& B) { int I; 1 d% b! p" G" I# q2 B if (B.Len == 0) return 0; xnum R; ' F t, B k/ p- ~6 o7 i$ k for (I = 0; I < A.Len; I++) { & f" U" C* F$ ^7 s hugeint Carry = 0; 5 g) B$ e4 J& z7 g# y3 G6 b! R6 A for (int J = 0; J < B.Len || Carry > 0; J++) ( E3 |- P) F4 ^. h( L; ^; e& [ { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; if (I + J >= R.Len) R[R.Len++] = Carry % Base; : z; m, y* H. ~" M' ?8 F else R[I + J] = Carry % Base; $ e# y2 v p( f; @( w% z Carry /= Base; } } return R; ' t1 E# D+ I, Q/ q5 Y0 E' k1 w}

xnum operator/(const xnum& A, const int B) { 9 x* ^8 w" J2 ?0 e& @ xnum R; ) s$ k2 e7 S4 I* C5 p5 C int I; " J' C; ~! G: W+ M; t hugeint C = 0; # h5 W# @1 k0 q0 g& _+ O+ e for (I = A.Len - 1; I >= 0; I--) 8 U0 c- f7 m6 e. {- f `8 a z9 g { ! P3 e, Y8 A" ~- M; y C = C * Base + A[I]; R[I] = C / B; - [& ~) m' {; H2 s4 z C %= B; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; # B$ L7 p9 W+ z1 c' ^: l# ?+ I return R; * n! O6 |8 }* I6 n, ]/ ?( }4 ~}

xnum operator/(const xnum& A, const xnum& B) { # y w0 k0 j4 x5 p$ h; y6 Q int I; xnum R, Carry = 0; 1 _+ f& d, {+ m: t0 ?1 S( d" x( O int Left, Right, Mid; 3 Q4 }9 @$ j9 y) x$ }$ ? for (I = A.Len - 1; I >= 0; I--) 0 R' N) B. f, W' U6 ^ { 9 P/ G' X% y+ N# ?/ V% L* w Carry = Carry * Base + A[I]; 3 O6 N5 ]8 v5 v2 C9 o2 f/ T$ s Left = 0; Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; + e# j% v% R5 v8 M if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } ; u5 g5 Y. b. T# o4 ~& _2 W R[I] = Left; % h2 @ x- v2 j" h y0 k" j Carry = Carry - B * Left; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; : d! r6 D1 u7 R- ]; E2 V return R; } % z' ]8 b3 ^+ d2 s0 nxnum operator%(const xnum& A, const xnum& B) - s) x5 f+ ?8 [$ W; }- Y{ int I; 4 j8 h1 c: C1 U xnum R, Carry = 0; int Left, Right, Mid; 2 M' B+ ~! W9 Y$ W% ] for (I = A.Len - 1; I >= 0; I--) { # H3 K9 o5 N$ g$ n9 a0 I; N Carry = Carry * Base + A[I]; ! F1 L, R1 s6 q" t0 O Left = 0; Right = Base - 1; while (Left < Right) { & s& q: M; |' ~* }! S( M4 i Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; 7 _3 b1 m; Q* R* ?. a7 _" J; S, F, R else Right = Mid - 1; & _! \4 U- I8 n- j& Y } 0 Y4 Y9 t. D) m) Q R[I] = Left; Carry = Carry - B * Left; * \1 n/ N8 q; H& e/ h9 G6 Q } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 2 n6 c' Q- R; B2 { | return Carry; $ U5 m2 H a- k5 g9 V}

istream& operator>>(istream& In, xnum& V) { 9 t1 H: w7 | y char Ch; 0 M7 T; P d. r8 y; |: b for (V = 0; In >> Ch;) { V = V * 10 + (Ch - '0'); 9 h& G/ z. a3 |) N if (cin.peek() <= ' ') break; } return In; }

ostream& operator<<(ostream& Out, const xnum& V) { int I; 1 b' s+ J p# ~: W2 b5 C4 z$ _2 ^4 R Out << (V.Len == 0 ? 0 : V[V.Len - 1]); 5 X1 t0 R' ?; T$ L2 Z for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; ; {. C# D9 ], f1 k return Out; & x) ~5 z5 W- G7 r2 P u4 E' S}

wangjiaqi49

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

cshdzxjtu

强！