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

xuefu998

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

" ?/ y* N( ^0 U# L

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> ! u& C: Z6 W0 M' I; B7 i6 b# include <string> using namespace std;

typedef long long hugeint;

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

struct xnum { 2 F) @$ Q$ k0 L. k. P2 X int Len; int Data[Capacity]; xnum() : Len(0) {} # \! R+ i& o$ Z$ `/ |! q6 I xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } ( G9 g1 M4 h5 c/ @( w xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } - S" @, a, X& Z xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } + F% _! e1 f. ^0 @) V2 B int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } };

int compare(const xnum& A, const xnum& B) { 6 P7 D* n+ \4 M/ ` int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); if (I < 0) return 0; 6 k: n" r g" D: Z6 a return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) { + E6 }4 a% j5 l+ Y+ m) P xnum R; 2 N4 q* X- X6 j: K/ V( p( K% L c) j int I; , g u5 P& {6 v( Y int Carry = 0; 9 I1 | K3 n7 |# j. G for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { , G9 a6 a3 X$ U: A1 a* d* I* v if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; $ J1 T8 |3 J( y, { Carry /= Base; , f [7 H8 F# Q Q. E0 w, H! t } R.Len = I; . C: W! K4 e. \2 A- \2 ` return R; }

xnum operator-(const xnum& A, const xnum& B) : B( O- B P" k5 ?{ $ A: Y7 E" N; k& F% c+ [ xnum R; U9 m5 C0 ~2 u- T+ Y) E9 |, ? int Carry = 0; + a, U+ R) _ E* Y! c R.Len = A.Len; int I; for (I = 0; I < R.Len; I++) { R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; 2 M6 |9 w" J5 @* I# k if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; _; D/ Y! \9 j# P! u% T5 Z } 7 p7 }' V. H" b- p& j3 z while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 0 X. _5 c$ O* R3 y0 p$ [ return R; }

xnum operator*(const xnum& A, const int B) 4 Q* t/ r9 G* Y% `{ 3 y1 g; D. x9 T6 ~9 {) D int I; 5 j8 l" z, Z' w' V# W9 }- S8 ] if (B == 0) return 0; ' g, v3 v+ T" K" G0 I% Z xnum R; hugeint Carry = 0; 7 F4 p8 a% M/ x$ C9 M for (I = 0; I < A.Len || Carry > 0; I++) { if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; Carry /= Base; : N+ {7 }3 g. n } % j* E7 [/ {$ S5 ?) ^ R.Len = I; return R; }

xnum operator*(const xnum& A, const xnum& B) : R! A5 {5 |- X( m3 o7 e1 @, g: |{ 4 o1 C; }3 W4 y" t& a7 `$ E int I; if (B.Len == 0) return 0; & ]+ m5 {2 h$ b) N- n xnum R; for (I = 0; I < A.Len; I++) & m1 Q! K: N5 S' `+ { { hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) 4 \9 U' Z. z) T, _' P/ |9 C { " g) }8 Q& E1 s) @# } if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 1 L3 y; W; j/ Y7 w |; R7 r if (I + J < R.Len) Carry += R[I + J]; if (I + J >= R.Len) R[R.Len++] = Carry % Base; 3 k$ { g% c5 b, i else R[I + J] = Carry % Base; }9 p Z, s! Q6 N4 H+ `% @2 i E Carry /= Base; 6 Z8 h, P9 l: o8 O+ v' Q } 1 a" X% f( r/ b6 a/ u2 ^ } & l `& }0 X) e; x& z' x7 ] return R; 0 u X* [" S' d% t& k: ?9 p}

xnum operator/(const xnum& A, const int B) { xnum R; ! p. _) M9 B' a+ G8 o5 r- m int I; hugeint C = 0; ' v9 n0 n: J+ i- ~! P9 c3 y for (I = A.Len - 1; I >= 0; I--) { & Q8 z( C! |: \" O) q C = C * Base + A[I]; 8 k0 E: \2 u" w- b/ p' ?- ] R[I] = C / B; C %= B; } R.Len = A.Len; ' i! Y' J6 p- h7 C! I$ o while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator/(const xnum& A, const xnum& B) 8 H) y6 h% [# W& g{ 7 w+ ~# Q! q" l: E int I; xnum R, Carry = 0; 1 ~. L& ^6 `2 T4 f6 G7 O( Z int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) 0 t. R- d/ |. [$ s, v2 G { ( |; N7 n+ b, d# N Carry = Carry * Base + A[I]; Left = 0; Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; " e6 q( R9 @- c$ q } R[I] = Left; 5 A- b+ j; H0 f Carry = Carry - B * Left; } 2 I1 U5 p* R8 t ?! V" E" _ u' b9 F R.Len = A.Len; ) a# n; C, w- {! Y. ~5 u0 O while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 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; ; Y c, T5 n8 z5 B x* |7 O1 ] Right = Base - 1; + H( \+ g, F# U. a8 E while (Left < Right) 2 l: q3 l1 T, c' R: p { Mid = (Left + Right + 1) / 2; , o9 w9 B2 ?, a+ o- p if (compare(B * Mid, Carry) <= 0) Left = Mid; . E3 F" ]1 V% h+ ~+ z else Right = Mid - 1; } R[I] = Left; - t% r, x3 O# X8 _/ ?# a Carry = Carry - B * Left; 1 R6 n f# Q7 f& e# F) i" r4 C- E } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; " D! { K0 a% r}

istream& operator>>(istream& In, xnum& V) $ F; A. h: H7 N/ b{ 6 Y; L& o' u) L& ?1 G: ~ char Ch; % {! Z6 j# y3 G1 D for (V = 0; In >> Ch;) ) i4 c" o( l9 C |* y { z0 j) {# @4 H/ x" v V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; } return In; }

ostream& operator<<(ostream& Out, const xnum& V) ; `) C7 W7 ?# b* w( w{ / k5 q0 i' \) j/ h* L5 j int I; 2 r% M$ r' A0 R) ]) t0 I 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; return Out; 2 V1 r u- p& Q} 9 M9 x& ?" Z9 r: Y+ P: ~. u

wangjiaqi49

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

cshdzxjtu

强！