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

xuefu998

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

% k/ I+ p$ j' p! B3 W

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> ) @. n6 w) ^( n1 M; Z#include <memory> 1 A/ C2 M# R+ d9 }+ W% v/ p1 w# include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; ' \9 r! ]% ^* l8 ?' O: oconst int Capacity = 200;

struct xnum { ' [- |# T O9 V8 X! L! W int Len; int Data[Capacity]; xnum() : Len(0) {} : m8 W4 I! a, a3 o; r- C xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } 6 i0 {( @ e c! [/ B8 ^ xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } ! p8 u1 W! l7 J( N, {0 t! u* c xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } int& operator[](int Index) { return Data[Index]; } 8 {% t0 P3 ~: q% \6 c8 J7 D4 X int operator[](int Index) const { return Data[Index]; } + C# d1 V+ d0 ^5 \" i; @5 f2 B};

int compare(const xnum& A, const xnum& B) { * l. X5 A1 v* D4 i7 w$ a; E int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; ; Z. K0 T6 P8 H5 R. K! m for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); if (I < 0) return 0; / }( `4 v& {( V- E/ A. |- \; b return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) { xnum R; + o& q; S# w V! l8 H int I; 8 w1 D }# a* r int Carry = 0; 0 j8 W" O; D$ o" J- r for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; , ~. Y& E9 ^% J Carry /= Base; - a( `. _/ T& h% T; a% ` } R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) . A' t8 @% M- @) e0 B5 Y{ 1 P) i# { ]5 g0 u0 ?" E% m xnum R; 4 i! Z7 y! g; @. w' ` int Carry = 0; R.Len = A.Len; int I; $ F2 |* n8 G/ F e$ X6 i for (I = 0; I < R.Len; I++) { 7 Q W; X+ E" j4 D5 c0 {4 p R[I] = A[I] - Carry; 5 Q- G& u7 [. [7 K8 m0 C if (I < B.Len) R[I] -= B[I]; 0 F4 ] k9 D4 D4 ^ C0 y( d, K! m. J# V if (R[I] < 0) Carry = 1, R[I] += Base; % W* V5 T# q; [4 ^! {, O) c else Carry = 0; 3 Y' u" P& \' X, v# M( { } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; * S: |2 r( f/ C$ [: m% z Y return R; 3 P: U5 z$ P X0 g2 ?, j}

xnum operator*(const xnum& A, const int B) { int I; # u9 P. y/ d, t: p if (B == 0) return 0; xnum R; hugeint Carry = 0; for (I = 0; I < A.Len || Carry > 0; I++) . x0 u5 Y/ W# u }3 p$ G1 d* F { . w% \8 R* c8 r& C& t% { if (I < A.Len) Carry += hugeint(A[I]) * B; - m ~. H5 x& K2 M1 d R[I] = Carry % Base; Carry /= Base; } R.Len = I; return R; / y/ z; @' D5 f1 ]}

xnum operator*(const xnum& A, const xnum& B) { int I; if (B.Len == 0) return 0; 3 X3 n8 x! @) l1 `2 @$ b9 A xnum R; . d( L, H8 h& U for (I = 0; I < A.Len; I++) % i; q' x$ L+ H8 O! M5 u5 I { hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) : X( M( c Y1 C7 d: y' f { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; " T& A8 R' ^2 }7 G* z) B8 W5 Z% Y if (I + J < R.Len) Carry += R[I + J]; 2 D* k( \7 D9 q g* X: P1 q if (I + J >= R.Len) R[R.Len++] = Carry % Base; ) o& Z! w9 [* g( P( ~ else R[I + J] = Carry % Base; Carry /= Base; # P9 I$ w4 s' e' f6 n } } 7 [% l: `1 b/ M& J return R; }

xnum operator/(const xnum& A, const int B) ' W/ i; ]8 H" \3 }# Y{ - N, W1 p7 n2 L" [+ N3 c" ~' ?& W xnum R; 9 i1 e, k5 d2 P int I; ' m# U& ~7 G7 p* e- Z hugeint C = 0; ' L6 N) c- T. R; A for (I = A.Len - 1; I >= 0; I--) : y9 u* F) I H) E$ U# s0 T { 1 J% a9 N1 u' ^ C = C * Base + A[I]; R[I] = C / B; 0 `6 a- ^+ J& k! h$ T C %= B; 8 s q) b( ?1 P1 n1 K } - \9 U& ~+ h8 `( Y9 ~ R.Len = A.Len; 4 O- O- v8 {) z- A$ q while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator/(const xnum& A, const xnum& B) # R3 k$ F) m) Q" w9 J( b" e3 A{ . z. l. v% G: S4 E int I; xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; 4 m4 J3 M3 Q5 u0 A Left = 0; - O0 l# i: O) Z) F- ~& } Right = Base - 1; while (Left < Right) { # L0 _8 z8 D1 ]+ \' v) }+ A5 U Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; 1 Q' w$ R* @4 n } R[I] = Left; Carry = Carry - B * Left; } 7 q% ~& ]4 z4 Q R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; } xnum operator%(const xnum& A, const xnum& B) ' H! s. [: X% j8 X( C{ * s3 h X* Q. K' @; z int I; xnum R, Carry = 0; 1 ^2 p3 F+ B- ~0 D( t$ V7 r int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) 6 J' e9 ~# W4 x- m# Y { 9 O; L6 {( [ A! y) w Carry = Carry * Base + A[I]; 3 a$ y- ~ ]- E* v Left = 0; # x+ F/ t9 N8 m' ?0 W0 Q: `1 V Right = Base - 1; $ _% L% x; `- n while (Left < Right) { $ w$ f( I- ] P2 R f Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; 5 K) J s2 `" N' _ else Right = Mid - 1; ) ?$ u8 U2 _" P: C6 w } 8 J5 g7 g d2 ?% ?* ~ R[I] = Left; Carry = Carry - B * Left; } 3 Z& m8 n% s3 y- c, u# u1 }% ]0 \( ` R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; }

istream& operator>>(istream& In, xnum& V) { # R& I: t7 ^2 s7 f& M; D char Ch; 6 L9 q1 i) ^$ h) G for (V = 0; In >> Ch;) { 9 e% |) _7 f, o S$ i, I V = V * 10 + (Ch - '0'); 9 B3 t7 b4 {0 C* h4 X if (cin.peek() <= ' ') break; 2 ]! x$ c: S7 M& a: l1 ^ } return In; % y3 [( x2 g9 J F A}

ostream& operator<<(ostream& Out, const xnum& V) 9 M* F7 }2 ]) N% V/ P: p9 A{ . s1 B# ~! h$ {. [% @ int I; . ^4 s# B- Q1 b 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; : h Y& n W( D5 n7 f return Out; }

wangjiaqi49

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

cshdzxjtu

强！