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

xuefu998

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

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> ; `7 d$ C, o2 ^. S( d" U#include <memory> # include <string> z v M. ? x& a# @# @using namespace std;

typedef long long hugeint;

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

struct xnum ' r# V6 e: U% b0 D! g( h{ int Len; int Data[Capacity]; xnum() : Len(0) {} * F1 Y0 N6 K; C0 G. l xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } " Q: j* `, n) M/ r$ E& t! Z 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; } " z- j* V( [- Q0 Y9 B int& operator[](int Index) { return Data[Index]; } ' q9 H0 J, ]' Z% S' C6 v int operator[](int Index) const { return Data[Index]; } M/ C! d6 x f7 L. ?3 z};

int compare(const xnum& A, const xnum& B) - m2 m! J) E) P/ m{ int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; . ^, L$ L5 L7 `- t 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) 7 d6 h/ Y$ a) ]+ J{ / l$ @* u0 Y1 b1 |4 ?( x" w R xnum R; 6 I8 S# q! K: ]1 j' ]0 t int I; int Carry = 0; ! L* r, N- K9 |, L for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { if (I < A.Len) Carry += A[I]; 1 F, W, Y7 o8 d, U, r0 d if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; Carry /= Base; 5 O. p, r3 l# [. k' T } R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) { xnum R; int Carry = 0; R.Len = A.Len; - r2 `3 u# P" u7 _& \" B int I; for (I = 0; I < R.Len; I++) - y$ W/ y! u w+ i { R[I] = A[I] - Carry; 0 @# I9 p3 V: c if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; } ' H$ X' M, p6 D5 O: G while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator*(const xnum& A, const int B) 9 m, N6 Z: G% c{ int I; if (B == 0) return 0; 8 Y1 h# G+ O$ P5 k xnum R; 4 B/ T: V6 M! v hugeint Carry = 0; for (I = 0; I < A.Len || Carry > 0; I++) { + N1 B; W# U* L, K' r8 w J if (I < A.Len) Carry += hugeint(A[I]) * B; 9 f1 _' p5 C# @8 {) l9 ?, j6 L y R[I] = Carry % Base; 4 n0 {5 S! [( v0 k: S Carry /= Base; ' u2 s0 H$ Y3 }) y S' t } 9 o8 m0 p$ X ]( K R.Len = I; return R; }

xnum operator*(const xnum& A, const xnum& B) - B1 e8 O0 o) Y{ 0 w8 r- e! n6 ^% a+ M9 a9 `: u int I; " ~5 Z, |0 {8 V$ a/ S. A9 n! L8 E if (B.Len == 0) return 0; xnum R; for (I = 0; I < A.Len; I++) 9 k b$ S, C# S; M { " s0 k8 s/ y+ Q* ]" s7 p2 T# z hugeint Carry = 0; + _& g% k4 g* S1 d3 I for (int J = 0; J < B.Len || Carry > 0; J++) $ Z7 _9 Y1 @6 ]% V+ O, R5 t1 h { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; N7 ?6 m$ [) } if (I + J < R.Len) Carry += R[I + J]; if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; 1 c7 F9 L, N0 I% {: X Carry /= Base; } ) }' }, R# M' x* Z6 \6 j+ t/ m } ; ^- U( j7 j- q% R3 ] return R; ; i8 e/ h& s0 d& x# ?6 g}

xnum operator/(const xnum& A, const int B) - h% t4 j. m, V$ J7 A g{ xnum R; % V: U# G! X: T W int I; hugeint C = 0; 3 P1 m6 T% N8 ]2 G# a- Y for (I = A.Len - 1; I >= 0; I--) $ I/ {& R% x$ e7 N5 b' q5 j, y { ' o& o# l a6 K. H C = C * Base + A[I]; R[I] = C / B; / I* b0 X7 L% o8 c& i% u) H0 n C %= B; } ( ?2 E9 `9 B0 u- R+ d/ [ R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; / J$ ~( \% W. e0 l/ J return R; 1 y) @- _* ~7 L}

xnum operator/(const xnum& A, const xnum& B) ( h! A& r# o; n/ K{ int I; : I0 X w3 W' n1 u, | xnum R, Carry = 0; 4 ], e6 u6 K% E1 n int Left, Right, Mid; 0 R# ^1 v* q4 |6 F) ?4 i6 q2 k for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; Left = 0; " G) w% J" s4 @5 q0 u& ]' E3 I Right = Base - 1; b; L, Z. [7 g* _% M* y while (Left < Right) { Mid = (Left + Right + 1) / 2; 9 n& f% C6 B: e6 F if (compare(B * Mid, Carry) <= 0) Left = Mid; & H0 l" m3 K: l; x0 U$ Q- N1 E else Right = Mid - 1; } R[I] = Left; , `' p8 k4 ~0 X Carry = Carry - B * Left; + q1 ]3 `+ V5 U y } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; } 3 t& B5 c3 C" g V! c' O. Z* _# Sxnum operator%(const xnum& A, const xnum& B) 5 C% G" v* u. S; w; K{ int I; % J1 Y6 Q" H( L2 v# n6 ]+ D xnum R, Carry = 0; int Left, Right, Mid; % y% y& c7 P) Q* {6 W for (I = A.Len - 1; I >= 0; I--) { . y% z3 `8 ^% F! D- k: p0 U Carry = Carry * Base + A[I]; Left = 0; + V( x6 y* w1 d% W- \% d Right = Base - 1; ! @9 K3 |3 C2 ]/ K0 A% b c while (Left < Right) - z5 }" T9 l0 t7 O+ \. D9 `2 u( j { $ p) Q3 J4 n* W Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } R[I] = Left; & v4 D9 ^9 ?- W- C* s; h Carry = Carry - B * Left; 4 R3 F7 m) ^0 F7 ` } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; % Q$ s# v3 i& P& v8 w}

istream& operator>>(istream& In, xnum& V) { , q+ F) B/ U6 k/ w5 y3 e) J char Ch; for (V = 0; In >> Ch;) { , k; c: f% e: M ?- L' D4 c V = V * 10 + (Ch - '0'); # `9 @, t" v# z7 i$ c if (cin.peek() <= ' ') break; , m( o2 D( n4 r4 |5 n0 A } 4 f/ H; {! m6 B& T L9 D4 e return In; }

ostream& operator<<(ostream& Out, const xnum& V) * H3 l/ E, \7 R& \. O0 {2 {{ int I; Out << (V.Len == 0 ? 0 : V[V.Len - 1]); " y- n" s4 {# r, I! ^ for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; , c* f6 \9 z0 t# T return Out; 0 d3 m$ x7 I2 K; X8 F- S& ]} , j: @( F* F7 d

wangjiaqi49

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

cshdzxjtu

强！