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

xuefu998

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

3 {# l0 H9 Q7 G5 b" J" B. q

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> 7 u& e# l1 f& ^1 c( M+ o#include <memory> # include <string> & a; j0 _+ Q1 j, X4 o0 W% T/ i) |using namespace std;

typedef long long hugeint;

const int Base = 1000000000; : J g& w0 p. [0 W n2 P$ Jconst int Capacity = 200;

struct xnum 4 n5 d+ ? G' Q3 @# i; z! A{ : H8 {1 y. L w0 c! T4 r( @2 E int Len; / d# K6 G" w$ y3 L int Data[Capacity]; % ~. u8 h6 L8 _% f- J2 o! y) x/ W" J2 k xnum() : Len(0) {} 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; } 9 M# Q" e o) F9 Z2 A% i xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } };

U1 m, p4 i. G9 iint compare(const xnum& A, const xnum& B) 1 ] J- j- V& K, F{ ! c. i7 o0 p/ G$ F/ u# N int I; h* Q* \1 I3 L: ]6 s) z. s' T7 P 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; 1 ~( i7 \7 w5 z: s return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) * n8 j# a3 h1 \{ xnum R; int I; 2 `7 G! D" O+ ?/ j int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) ( g3 ^- w3 m! _6 i! M* ^ { if (I < A.Len) Carry += A[I]; - A% y. @ I. L& X if (I < B.Len) Carry += B[I]; 4 ]* A$ p8 P$ e/ c# N% O3 A R[I] = Carry % Base; 2 v4 L: l5 Q! x; y Carry /= Base; } R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) { xnum R; 8 i: O) t4 D7 R+ t. m int Carry = 0; 4 ^$ m$ E3 g) K9 N5 k0 o- ~; S/ q% w R.Len = A.Len; & J! q' I' B6 g0 j int I; * a$ J' {0 ]: F* a for (I = 0; I < R.Len; I++) { R[I] = A[I] - Carry; 1 a7 K& v# }6 m( n+ J% O if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; : J* F* ?0 N% P& _* h else Carry = 0; } 7 @5 g1 [1 l! j- k: c; F while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator*(const xnum& A, const int B) 1 K/ ?% N; _# a+ g, J{ int I; $ X2 b9 n7 B; a+ O/ f+ U& X; S if (B == 0) return 0; xnum R; hugeint Carry = 0; * u4 m4 ?; E) S; i for (I = 0; I < A.Len || Carry > 0; I++) { % i! P2 h1 \" [1 z, {' F; S+ L if (I < A.Len) Carry += hugeint(A[I]) * B; ) T; F% X `; R* C p( q; L6 Z, } R[I] = Carry % Base; Carry /= Base; : t( B1 ?8 q- X Z1 l$ f* H } . g* u( q) G8 y7 j- ^6 N: m n; J R.Len = I; " |8 F( V, i. e) n# Z$ k& D+ P return R; }

xnum operator*(const xnum& A, const xnum& B) 4 _' o5 F. M& c{ , C- [+ `) B: Z7 P/ N2 x int I; if (B.Len == 0) return 0; $ Y" \, @7 t/ R4 b xnum R; - N' F6 O2 z+ j" @7 b v for (I = 0; I < A.Len; I++) ; V! {! @. n- C0 P. N; C$ ` { 5 g/ E7 |1 ~% {1 m, ^ hugeint Carry = 0; ( }1 a: @0 t' o# F2 \/ v4 [: X# ?# A for (int J = 0; J < B.Len || Carry > 0; J++) 9 C+ z! b, x" g1 _ O2 q { 6 ?$ n0 L8 X5 U8 ^# R if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 7 y- m0 O! A2 F+ u; v r$ a/ d if (I + J < R.Len) Carry += R[I + J]; ! o+ _7 I6 C2 u7 M0 L2 a0 E if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; " Q4 L8 {9 Z/ M+ i- k Carry /= Base; n( E/ f: A( d$ R8 E& Z1 V } % K. g8 M7 l* V } 0 U% j2 D d( | return R; }

xnum operator/(const xnum& A, const int B) . g1 }) r" q! L1 J{ 0 G, g" _* x0 b/ [/ P5 N xnum R; int I; 3 A ]: r' U. d/ g" [( q7 g hugeint C = 0; " o4 I- C* r# B/ H6 j U7 C for (I = A.Len - 1; I >= 0; I--) . ^ [3 B& ^; \# G& @5 ^. \1 s { C = C * Base + A[I]; 4 }8 x) R4 g" O" M% _ R[I] = C / B; * {. K/ t$ Z" \: y C %= B; 5 _7 e7 Q$ o( [: t+ c) Q } R.Len = A.Len; ! m. J) C3 `, ` while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; : P+ x; h2 S' R, [) c' c return R; }

xnum operator/(const xnum& A, const xnum& B) { + e" V% C$ C# m, M! r( m' v5 T7 i int I; % i' W& e0 I0 q; k8 v1 [ xnum R, Carry = 0; + o! x0 ?5 \6 B3 X7 ]7 \* i( y int Left, Right, Mid; ! X) L$ U4 c: S for (I = A.Len - 1; I >= 0; I--) 8 @5 S! S, _1 A, O$ m { ( s: I1 Z+ x8 [; T! K# \ Carry = Carry * Base + A[I]; % A' h% e( o- V5 W [ Left = 0; " K4 Q5 r5 T5 }- d+ J; ^- g Right = Base - 1; , q: w4 x' _# d2 @ while (Left < Right) { Mid = (Left + Right + 1) / 2; ( `# z6 J+ o4 U. p1 z if (compare(B * Mid, Carry) <= 0) Left = Mid; . p' T& Q$ k: f* A else Right = Mid - 1; } 3 y8 G, T4 s: {' [8 N1 F R[I] = Left; Carry = Carry - B * Left; : K+ T8 a, }5 c7 ^/ q: O. e } # s1 n( d: I+ @' y2 q& G R.Len = A.Len; 6 g; @6 x8 ]; ?9 H6 y while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; } # q- |7 h) D5 T2 s8 d5 B# ixnum operator%(const xnum& A, const xnum& B) ! _) Q# k6 H( F! q: B+ p{ 5 s: Q# \8 [8 N O" B7 U4 y8 f int I; xnum R, Carry = 0; int Left, Right, Mid; 6 N. F% Y, C/ a2 U6 S7 B for (I = A.Len - 1; I >= 0; I--) { 7 V( Y0 w8 M9 x9 y! J" M, z& q Carry = Carry * Base + A[I]; 8 b4 W; c) Z+ o! j' ~, T# i Left = 0; # n: ]( p: d# Y L, c Right = Base - 1; ; l" O2 G4 K8 D% L8 V* V& Q8 R while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; $ n9 m. n/ R& O# U! {7 _4 J" H' N else Right = Mid - 1; } R[I] = Left; ( ?! V s: W D Carry = Carry - B * Left; } R.Len = A.Len; # R; V- S* _' ~6 Y/ {3 s while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; # n/ d0 b/ ?" O1 n( V return Carry; }

istream& operator>>(istream& In, xnum& V) { 5 a# g @4 H, i& R char Ch; for (V = 0; In >> Ch;) : C) V& a" [8 x8 k { V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; G( K/ s. o5 K% y } return In; % W+ U8 P! _5 n, z}

ostream& operator<<(ostream& Out, const xnum& V) % ~3 }; i3 ]) x6 T{ 9 ?2 Z& p8 Y: i$ _0 H8 P int I; 6 G: T5 s6 L U% F9 `( z/ Z 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; # {2 \6 c0 Z1 J$ p+ P return Out; } : M7 ~3 J0 H/ k+ T5 A# f8 k3 x6 l! s

wangjiaqi49

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

cshdzxjtu

强！