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

xuefu998

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

2 g4 ?4 l7 s! x; C7 q5 G9 P$ n

现在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; , q0 l! e K3 p, Uconst int Capacity = 200;

struct xnum * _4 A$ @9 b$ S+ P' r{ & N7 y$ n% O( c/ l# p6 p9 G: S- o int Len; ! Y k( q) }- X" d* w8 K# z5 } int Data[Capacity]; 6 z+ ~- x' J* ?+ {, M3 l; m xnum() : Len(0) {} xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } 3 R# }2 Y$ l6 C1 q' A$ ~% K 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; } " [ ~5 b$ T$ E8 j9 k) y0 V0 ~ int& operator[](int Index) { return Data[Index]; } 4 R7 [7 f8 n6 e' i5 ~' R) @ int operator[](int Index) const { return Data[Index]; } };

, D1 V( H5 h( n! P0 J* G" xint compare(const xnum& A, const xnum& B) { int I; " X: V. {5 N9 r$ t Y' T" K if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); * o) J4 f; L& n4 j+ ?, t- i; D if (I < 0) return 0; return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) 5 F. D) l/ t( G$ ~{ xnum R; / n' `( W8 e2 i int I; ! R* ^# Z- H! B5 ^6 B int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) , l; C* {3 C1 [3 `6 b { if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; Z" E3 P; \+ u' o Carry /= Base; 1 A* ^& H1 e- j* P% {% X; B } % D7 v% e+ | n% M! } R.Len = I; / Z* g/ L& q/ i: w @, h return R; }

xnum operator-(const xnum& A, const xnum& B) , ~3 \* X( Z# n. V{ xnum R; int Carry = 0; - S0 b" X9 J/ H6 k8 d R.Len = A.Len; 9 I3 M/ ^' N. F5 G/ ]( r int I; for (I = 0; I < R.Len; I++) { R[I] = A[I] - Carry; 3 Y( V( @( \ N; S7 _$ m7 n& R8 Z; A if (I < B.Len) R[I] -= B[I]; 5 y( j u P; r1 b3 `6 | if (R[I] < 0) Carry = 1, R[I] += Base; " w4 U: V9 p1 \5 O0 E else Carry = 0; } 0 I6 K: e' y' E: t while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; * F0 p) G K D return R; $ K. f8 j" K0 c}

xnum operator*(const xnum& A, const int B) $ k9 l! j6 @. C: l6 P! U{ : m& m2 t) M' y) j5 |! a+ } int I; if (B == 0) return 0; xnum R; * ~3 f" P/ i* r7 U" b6 b hugeint Carry = 0; ! Z, [$ n) E+ `, a( o9 r for (I = 0; I < A.Len || Carry > 0; I++) { if (I < A.Len) Carry += hugeint(A[I]) * B; - |9 Z/ \$ C( m4 I R[I] = Carry % Base; Carry /= Base; 6 V' R! \" P7 m2 _% g o } - x T; a- m8 K( b* m4 E* c R.Len = I; ! v$ I+ E( s" ^( I return R; }

xnum operator*(const xnum& A, const xnum& B) % H) z: O9 q: C ?/ I0 j( j' U{ % _/ i+ c; L$ o3 d! O/ V int I; if (B.Len == 0) return 0; xnum R; for (I = 0; I < A.Len; I++) { hugeint Carry = 0; * @/ {6 F9 ?( v' h5 M4 y for (int J = 0; J < B.Len || Carry > 0; J++) { 7 y4 r9 r+ D. |/ o0 f' E if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; # U( @0 T: `7 S8 q3 w0 V& P if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; Carry /= Base; } : N0 x/ u5 G |$ U" t1 M2 b3 r2 L5 h7 N } return R; }

xnum operator/(const xnum& A, const int B) { xnum R; int I; hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) / N7 Y" i2 [# J0 @0 W5 Z2 p { C = C * Base + A[I]; 2 ]" }% p) r. N R[I] = C / B; \! I% {$ o& @ C %= B; } 1 G% Z s( b% V0 C% p4 p R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; , P/ W2 K0 u6 I+ I* }9 z" z return R; }

xnum operator/(const xnum& A, const xnum& B) , _, o3 Q* Q# r8 W' K* N{ ( H, \/ T' j& S( K- W int I; % }5 H& S0 W6 |+ n* B# T xnum R, Carry = 0; + @* C; \8 U" ?6 j0 o- H' m int Left, Right, Mid; % h, a& u& D; T6 A for (I = A.Len - 1; I >= 0; I--) 9 b/ q1 n+ H0 X- Y& u { Carry = Carry * Base + A[I]; 6 O4 H1 h+ ^$ p1 W" c7 l Left = 0; % b6 f+ R- u6 c2 ? Right = Base - 1; while (Left < Right) ) x9 R0 G- b f* `6 N { + D5 r3 g9 @% l+ I, a1 V Mid = (Left + Right + 1) / 2; 8 j! b e& O, c4 L if (compare(B * Mid, Carry) <= 0) Left = Mid; 8 c! Y/ G0 k" p4 P else Right = Mid - 1; 4 w# Q7 |% V4 G } R[I] = Left; Carry = Carry - B * Left; } R.Len = A.Len; ; i) _! \; c* f while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; : v7 m" }9 q- s. T1 b8 Q( h+ \4 G# {9 J return R; } 4 f( U0 r2 q9 |+ g3 u* l1 o3 Q+ Uxnum operator%(const xnum& A, const xnum& B) { int I; 7 A. [4 ]8 h* S4 F xnum R, Carry = 0; 7 o) n" F& O# \6 b int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { $ D' u6 t( D8 F Carry = Carry * Base + A[I]; Left = 0; 9 E: R# O+ S8 ~/ F: k q8 o3 P Right = Base - 1; while (Left < Right) { 2 ^% d, w! w" N0 D* D Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; 5 P( T. s! u: s" {, ]* Z) m( N/ i } $ e4 i" t5 b, d3 j R[I] = Left; , c2 B, b' A* ~3 I7 d6 D. w% f: M Carry = Carry - B * Left; ; m7 ]5 ^3 _. r& r I ] } S! c$ U% K, T9 I9 v R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; # |4 `/ U, D$ [9 T0 W" N}

istream& operator>>(istream& In, xnum& V) { char Ch; 7 ]6 m, ^( P: A* w8 B for (V = 0; In >> Ch;) 0 h6 ~; \3 R' ]& e: T3 K { V = V * 10 + (Ch - '0'); ) E2 \) X/ h5 M& m. t9 \ if (cin.peek() <= ' ') break; 5 Q2 |3 X0 r2 F( q: C } - R+ q6 q0 n0 A' a) z# k return In; }

ostream& operator<<(ostream& Out, const xnum& V) - c0 F4 P5 b% J% @) w{ ( T9 z. ]7 [2 Q% b# y6 v int I; " v! W e4 Q4 f6 l Out << (V.Len == 0 ? 0 : V[V.Len - 1]); 9 D! ]1 G$ ?1 |1 Y, F9 _ for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; 9 g/ e5 [' R! J- p$ Y) m return Out; ' S! ~1 Z' d! d- V5 Y} # r O# |( C+ H9 b9 s V

wangjiaqi49

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

cshdzxjtu

强！