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

xuefu998

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

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> 9 Y+ z7 i* B, S) K6 J# include <string> using namespace std;

typedef long long hugeint;

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

struct xnum # _ G6 f& H4 b+ Z* V{ 9 c' V+ v: J- k% t7 U3 j int Len; 3 ~8 a& s5 e7 g int Data[Capacity]; 1 t* I& K' H2 K xnum() : Len(0) {} ( `3 ~+ m" i- y/ J 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]; } ' x7 s; j! q* N d8 w* Y: q int operator[](int Index) const { return Data[Index]; } S1 O" R' Y8 w# V$ Z; U0 P6 v/ L4 K};

& x0 N7 J [3 Cint compare(const xnum& A, const xnum& B) * l) @8 A O( M3 Q0 r0 E{ 4 W1 L8 h/ T; S, j$ e" j int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; ; i2 Z5 @9 P" W7 d# x- b- `5 K) o 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) { % w! p! J% m; r- b9 g& n xnum R; int I; int Carry = 0; J+ R! t6 ?7 S; _: X3 O for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) 1 M/ L! v( Z$ s: r5 S( C+ f# G# A { 1 m3 z: j& C* ?+ E. F6 e% M if (I < A.Len) Carry += A[I]; 6 Z# K. R5 U6 l3 x/ L- m if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; Carry /= Base; } R.Len = I; ( P3 U& H* P* Y$ C0 S return R; 9 u5 ~2 T U" m" g}

xnum operator-(const xnum& A, const xnum& B) ! t) `$ R+ ]- [* _* t( ]6 w{ [& Y. U/ `+ T" T6 S4 Q xnum R; & U" k$ g0 h2 t# F- t int Carry = 0; 1 }' r# ^$ ~ T1 Z# W U R.Len = A.Len; ' | l* K ~, v: ] int I; for (I = 0; I < R.Len; I++) _ _0 x9 e8 h1 g { R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; ( e6 X _, e3 ]& s if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; ) a4 i% Z- U. _/ i3 O! l/ U4 I } 7 ~$ K, v/ [ b! O while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; ( i% t' }! S4 ^8 {0 A return R; z0 b( J/ h/ c4 l; S7 ^' t}

xnum operator*(const xnum& A, const int B) { int I; & t9 l3 Z% X, Y' O* A if (B == 0) return 0; xnum R; hugeint Carry = 0; ; Q* y e p# ]$ e3 s for (I = 0; I < A.Len || Carry > 0; I++) { # B2 L9 D$ G1 T ^$ J: A if (I < A.Len) Carry += hugeint(A[I]) * B; W; s, v7 i2 ~ R[I] = Carry % Base; Carry /= Base; 9 C$ u6 A: k- ^, a. } } R.Len = I; 7 E/ `+ L8 C: f return R; ! n9 @* h q) T4 i( H}

xnum operator*(const xnum& A, const xnum& B) { 1 O) \3 @. v3 p6 P: S) E8 h& W int I; if (B.Len == 0) return 0; xnum R; for (I = 0; I < A.Len; I++) 2 i) g6 D* J* Y% ~3 {7 O { hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) 1 C% _# C- o* V- v& ^3 e1 c { ! V/ G- r6 N0 W" u) c if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; ) X, j. _( v6 q' F0 S, V if (I + J >= R.Len) R[R.Len++] = Carry % Base; & H- f0 A* @/ r# L& r* S; T else R[I + J] = Carry % Base; Carry /= Base; * c& q J! S8 H6 i% E } 6 Z4 i; I$ R3 u } - P6 a7 z& O* ~ \* z& V- y) U return R; }

xnum operator/(const xnum& A, const int B) 4 n) |- R6 c! {& e0 w K{ 7 C* _4 K/ Q! \& X xnum R; int I; 3 }7 B5 `4 C0 T* P7 S3 a hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) ! [4 A& J6 o9 }9 L+ o { 8 {1 s+ j4 U& L- r7 S$ i* G, s C = C * Base + A[I]; R[I] = C / B; : f c- q% X: l C %= B; } R.Len = A.Len; 2 q; a9 l; \: J& E6 A8 j6 ^ while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; , x) X6 s* F. Q! }' g" i# d/ O return R; }

xnum operator/(const xnum& A, const xnum& B) { int I; xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; Left = 0; Right = Base - 1; while (Left < Right) { , y0 h; T* I0 k, M$ t6 V" f0 K Mid = (Left + Right + 1) / 2; ( L( x$ i, c( u8 G, p8 F, \& H if (compare(B * Mid, Carry) <= 0) Left = Mid; / `9 J- @( n. v' ^ else Right = Mid - 1; ) u1 S# b e* p2 M5 A3 K } 0 n. Z4 h8 J. k: [; K9 e V& d R[I] = Left; ) z& C, i; k1 d: \ H3 ^ Carry = Carry - B * Left; } 2 e# ~/ c) o) X4 y5 C R.Len = A.Len; $ { V2 {" l2 |' x$ j R. {& D/ p while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 8 @: K) T$ h3 D: f2 T* c return R; $ J% O; l- e" C* c} " N. A, i0 W6 |! O8 h, y% r4 ^! {xnum operator%(const xnum& A, const xnum& B) ( ?$ n& ?8 {8 m{ int I; xnum R, Carry = 0; int Left, Right, Mid; : O# s G* y! g4 I, [ A for (I = A.Len - 1; I >= 0; I--) " \/ Z) Z+ J0 d, d* i; B( l, K { Carry = Carry * Base + A[I]; Left = 0; " d8 o) M" Z( P/ J: d: U6 b Right = Base - 1; while (Left < Right) { 7 o" d6 `$ H6 \6 @2 H; l Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; % O E# {7 R5 D1 `* w1 s } 8 U) n+ |* x1 N R[I] = Left; " R/ H' b% S1 n7 {! k+ k Carry = Carry - B * Left; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; # ]/ B7 p1 k) w8 N. J1 V. k return Carry; }

istream& operator>>(istream& In, xnum& V) { 5 O3 z6 D" H/ J b char Ch; 0 }1 y# {6 [- W$ J6 a/ F for (V = 0; In >> Ch;) ; n$ e* M0 }4 n/ q" M1 J: B { 4 t# f$ W1 ^9 Z) w" s3 `6 `5 ~6 Z V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; $ ?& N2 D& u$ o& J } 7 e9 H- X) Y- L return In; }

ostream& operator<<(ostream& Out, const xnum& V) ; d/ _+ H7 o9 A0 c" T5 u) F) x{ 2 A3 v7 P6 h, L! k+ Q% F int I; 6 U) {3 }4 U' i- p$ V3 t- \' e 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; $ \4 J: C$ o+ C. K" T return Out; ( p3 I9 z. x6 R5 m, ~}

wangjiaqi49

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

cshdzxjtu

强！