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

xuefu998

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

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> ( X4 Q c+ g, E) A' L# include <string> 4 D/ R$ n8 d2 s8 Cusing namespace std;

typedef long long hugeint;

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

struct xnum { . s, r6 J' p2 O3 G) n int Len; $ _4 m( F1 l0 E" ?# \, Z2 X5 h int Data[Capacity]; xnum() : Len(0) {} - q" k! v. J% [9 I. R xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } , Q0 }) C6 D" S( I0 q xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } C' g L5 ?& e" Y4 P% u6 C. W xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } int& operator[](int Index) { return Data[Index]; } ) _3 j/ N2 [* h t# m5 h8 F0 Y ?# v int operator[](int Index) const { return Data[Index]; } 2 D) E( w' ~ M};

% {0 } {" E1 F0 m6 mint compare(const xnum& A, const xnum& B) ' [ |5 g* m; n( n; }2 L5 K{ 6 q: n! K/ }& J7 m' q# h# E int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; - s9 O* Y8 s7 N+ b) ^) Z9 O Q for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); if (I < 0) return 0; ' n/ r& ]/ p/ D% F; o7 [ return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) 2 D* f7 d* N9 W{ j; i( f0 P$ F xnum R; ( {- {5 J8 L' o+ M- V int I; " t" U N! b; S g2 K4 K4 c* d int Carry = 0; . {% S7 q/ Z. z2 K+ a' V for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { 8 f. q" K ~/ M! u8 o) r# o6 ]7 I% G if (I < A.Len) Carry += A[I]; 9 T! a" s7 [8 J$ ?; m6 Z if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; 5 B: v! y0 M. B: @: H- Y Carry /= Base; } G" h( v' O# g# f! n R.Len = I; 4 r& j1 L7 w0 j: p return R; # Z6 F' N+ k- g6 m, V7 a( a- D4 L8 {}

xnum operator-(const xnum& A, const xnum& B) / I/ I* L9 p2 h2 X: b/ k; n{ xnum R; int Carry = 0; * ^$ K) x* S% t; `2 h R.Len = A.Len; . h8 t- I9 D- U4 f/ z int I; for (I = 0; I < R.Len; I++) { R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; 3 U, [# m2 D; J else Carry = 0; } - R) A, t/ T. O! [8 v1 H6 Y4 O while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; . |; C+ }6 V- m return R; }

xnum operator*(const xnum& A, const int B) ' e% C% K' R/ g6 g{ int I; if (B == 0) return 0; 6 b6 w2 I; p, I6 u2 r* L8 B xnum R; , _3 D# r' J1 B% `4 H9 @( y0 W9 P1 D3 H7 a$ P hugeint Carry = 0; ; S$ H' @: l5 O5 Z3 n1 D for (I = 0; I < A.Len || Carry > 0; I++) { * P& z8 _/ h( G* t% ?. n" }' j6 ]8 M if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; Carry /= Base; & m* k x1 f/ u/ I- U+ R4 \- X1 a# L } $ x$ {* k% A. v6 Q7 o0 t R.Len = I; ' O3 y4 p q/ P. d, f return R; " [' {* {- T& M- Y# c: B+ B}

xnum operator*(const xnum& A, const xnum& B) { int I; if (B.Len == 0) return 0; " x9 M8 w: @4 C7 ^: r6 K1 j xnum R; for (I = 0; I < A.Len; I++) { hugeint Carry = 0; : W! r1 Q* X- h4 M% r: |$ l2 q7 Y for (int J = 0; J < B.Len || Carry > 0; J++) { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; # @6 Q. I4 m3 `. V5 F; W- q1 n+ V& { if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; : f0 G" h$ O3 T) E( Z+ ]& B% B7 g Carry /= Base; - I4 w+ g& ?! e% U* Q" h: e9 x3 u1 {* J } 6 B6 [3 t$ p# d/ N1 k4 p' O% } } 5 x9 U8 J) J$ w. X/ L/ @* ^+ N; Z return R; }

xnum operator/(const xnum& A, const int B) % v6 n! ~4 ?3 c6 Z3 f{ xnum R; int I; 5 \. @* u8 @3 Y% J4 z8 i5 l% g hugeint C = 0; . t, s* ^ P6 f( G& b! x2 V for (I = A.Len - 1; I >= 0; I--) { C = C * Base + A[I]; 3 M1 u, x& Y3 A0 Z R[I] = C / B; C %= B; 5 |9 \5 R( G9 g3 B } R.Len = A.Len; ' m7 S w6 X h* j6 l, ` while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; : M6 }$ G8 p4 s6 Q7 W- ~! \ return R; 7 m+ u+ J- ~3 e}

xnum operator/(const xnum& A, const xnum& B) ) F' t: w+ Y6 s& R; U& |5 n{ int I; $ u6 a1 b! h3 d! v xnum R, Carry = 0; ' i! w* q f) S6 a9 S4 w int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) $ n; z- o) m. h+ w/ u { : H5 ^% n, \2 S3 _4 l7 u Carry = Carry * Base + A[I]; Left = 0; Right = Base - 1; while (Left < Right) { ) K, X3 Z4 z2 H4 ^- I0 Z0 Z) q; l Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } R[I] = Left; . W2 [- z2 N7 o |2 E Carry = Carry - B * Left; $ S: ?% y) U" g, N( Y. h } R.Len = A.Len; 2 ]# G- ^% r& |2 z# l( f9 t5 [* X, ? while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; , A; s0 ~1 }6 l& K return R; " k% I' O5 w- V: Q% {) A3 P} ) |, Q# w; U' {6 r; H7 R; Axnum operator%(const xnum& A, const xnum& B) { 1 r7 H& c \3 K6 \' S% G int I; xnum R, Carry = 0; int Left, Right, Mid; , R7 v( ]& G7 I7 q1 A for (I = A.Len - 1; I >= 0; I--) { $ g/ h y) w5 ] Carry = Carry * Base + A[I]; 6 O' u. U0 r( d$ P! s3 A Left = 0; Right = Base - 1; while (Left < Right) 1 S# `& C/ G- f* w( o { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } R[I] = Left; ( \+ o3 F) N" r; a% {" H% E7 d Carry = Carry - B * Left; 5 [* N0 p+ \8 j; O/ @( n4 ? } : c* K5 b+ C8 ^ Z& h6 }$ w9 q R.Len = A.Len; 4 {7 n* e" c+ [' K( g+ _, H while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; % [' J' N6 J v; ~9 m, E$ P return Carry; }

istream& operator>>(istream& In, xnum& V) 0 x/ u) f# e, l{ # K6 z# \9 S: A& b1 V char Ch; for (V = 0; In >> Ch;) { 1 g2 `4 p' \& x+ A; Q V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; $ H: K! e. [( }+ A; L } $ _" i. ]& [) Q/ k( I return In; 6 U+ V8 d4 |) D}

ostream& operator<<(ostream& Out, const xnum& V) ) I; v1 L3 m" Y: o, f8 Y{ - n$ m2 T+ D1 W2 x int I; Out << (V.Len == 0 ? 0 : V[V.Len - 1]); ; T0 N9 V1 { K. i for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; return Out; }

wangjiaqi49

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

cshdzxjtu

强！