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

xuefu998

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

X% q" T# w* y( e; F2 z

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> #include <memory> # include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; ' B( N( f. p# ^const int Capacity = 200;

struct xnum ]$ E: ` [3 @' ]6 z* Q{ int Len; int Data[Capacity]; ' U# H/ D/ P6 `) D, m xnum() : Len(0) {} ) a. V4 x: r; a. v/ o% r2 `3 q1 m xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } 1 I& |! z2 x. G, L, o 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]; } int operator[](int Index) const { return Data[Index]; } ' o- }& X1 S* P' n$ ]" p8 E7 \! Z};

( |/ ^; C# N2 Z+ Cint compare(const xnum& A, const xnum& B) 0 m7 R. b3 H# `$ X2 P/ o V{ int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; * `2 e3 g: J7 | for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); , R1 u9 y [6 H0 F' W if (I < 0) return 0; return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) { xnum R; - q5 ^& e' N3 g1 l5 M. p0 |) K$ A int I; + T. D* ]: U" F: t' L$ e int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) ' j; X# q1 z. u { if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; Carry /= Base; } R.Len = I; return R; : m& j" A' c5 K. U}

xnum operator-(const xnum& A, const xnum& B) . c. Y5 u* l( m$ ~# C s6 |{ xnum R; int Carry = 0; R.Len = A.Len; & @+ J- h3 T) B int I; for (I = 0; I < R.Len; I++) ) @' r# f/ s& o0 y% f7 z { R[I] = A[I] - Carry; 2 O1 Y$ v. u+ H7 c) K! j# m if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; 1 r" d2 X8 m2 S' a" L- x else Carry = 0; 5 a `2 p8 p& A/ e2 h- e; j, M } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 1 z: d, @$ c% S return R; }

xnum operator*(const xnum& A, const int B) W& e! r2 W: }$ g" r{ int I; if (B == 0) return 0; xnum R; hugeint Carry = 0; # ?7 f& t# T3 N# q& _1 q4 Q for (I = 0; I < A.Len || Carry > 0; I++) ! b( {4 S. x7 P% q0 j, u0 C { if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; Carry /= Base; 7 S9 Z/ R2 S2 y# d } R.Len = I; : P0 C* f3 j; v. `/ L( D, e1 { return R; ' E" r9 F, H5 Y5 v7 J}

xnum operator*(const xnum& A, const xnum& B) 2 k7 L: H/ a4 x! w4 s' v% j9 G{ " H2 q6 h2 ?& U' B, |) i4 i int I; & ~% o; ^0 h9 X7 l0 {+ }0 J' W7 ? if (B.Len == 0) return 0; xnum R; , l1 N( a8 h* x* v for (I = 0; I < A.Len; I++) , A2 B) v( L3 \6 \) B { hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 4 ]7 ?5 g: Y6 {4 m- ]! x4 Y if (I + J < R.Len) Carry += R[I + J]; 2 o& V( ?! `0 W" M2 q n if (I + J >= R.Len) R[R.Len++] = Carry % Base; 7 m B/ N/ c x B; a2 f/ t9 T. i7 R else R[I + J] = Carry % Base; 6 ?: x3 {% h* y) w, }7 I Carry /= Base; # l6 Y* V# B5 d4 Z5 r } ) b: @) J4 N9 a1 L5 }9 D4 t } return R; }

xnum operator/(const xnum& A, const int B) 7 N2 R9 L. Y; {: g* a{ xnum R; ' L u4 l$ W2 G) V Z% ~ int I; : _8 Y3 ^- H( w* m- `& H5 p3 Y8 } hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) { C = C * Base + A[I]; & V' a) c U4 C2 m& t& Z R[I] = C / B; C %= B; ; R8 ~6 c2 M1 g: S# Z1 H$ s } * w/ i1 P+ N7 d; [ R.Len = A.Len; 1 ~7 S5 ]" [7 T g8 @& T while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; , }' a/ g; S5 s5 f4 L return R; }

xnum operator/(const xnum& A, const xnum& B) ) e7 o3 d1 W/ v6 r" S{ int I; , @4 e, [* d- _4 j3 s @ xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; - p- A# o5 Z5 ~9 d: z) k3 W! F Left = 0; 5 W. i* }$ f) T3 |- v! g Right = Base - 1; ' K1 U/ V; A1 _1 K$ w$ m while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } 0 b1 j9 `, G7 h R[I] = Left; ( X1 N' h. A! b# N$ X V" t' W. U Carry = Carry - B * Left; # R- \1 F5 p% ? I" N7 [6 G } R.Len = A.Len; 0 I4 G+ g& [7 ?* M! D9 Z: I7 b while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 9 D- q7 H( v( p( b8 n$ Q$ h return R; } xnum operator%(const xnum& A, const xnum& B) , [( T0 N6 {2 Q( x; }{ int I; xnum R, Carry = 0; l0 L; ^7 P, N, y int Left, Right, Mid; ! x- E4 c: Q; @- F6 Z for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; - ]3 {; K$ R/ v4 {- l0 c$ {& G Left = 0; ! x8 v3 W7 _9 y; B& x Right = Base - 1; while (Left < Right) { ' A9 s0 C' N5 m1 q Mid = (Left + Right + 1) / 2; $ x* F ], {# d5 r if (compare(B * Mid, Carry) <= 0) Left = Mid; % H5 I7 S4 e, { else Right = Mid - 1; } R[I] = Left; Carry = Carry - B * Left; } R.Len = A.Len; $ c1 @0 P3 f9 { while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; , V& M: p( w* h$ U5 _ return Carry; B' j% b) q/ w3 m8 u% O}

istream& operator>>(istream& In, xnum& V) { 8 ~8 g1 o( Q' ^2 ]4 y char Ch; 9 [3 K2 @4 K/ A* Q; m4 P# b for (V = 0; In >> Ch;) { V = V * 10 + (Ch - '0'); , l0 p: ]& y/ X( R if (cin.peek() <= ' ') break; } return In; }

ostream& operator<<(ostream& Out, const xnum& V) { % b4 B/ @" \/ P4 f. T, d! Z$ v& |6 R int I; ' D, F' Z& D0 s" A3 q [ Out << (V.Len == 0 ? 0 : V[V.Len - 1]); ; m R; ?4 U+ L( U d for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; 8 R \0 {' H; { return Out; o& N! t0 {0 E; X& R3 s5 z} $ Z; x3 s- m/ K* o: P1 \

wangjiaqi49

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

cshdzxjtu

强！