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

xuefu998

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

. U$ w7 @1 P* ]4 D+ y

现在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; & Y/ ?$ m. W' r2 ^, d$ rconst int Capacity = 200;

struct xnum 5 @; ^, X' [0 M" {" V, R{ " G5 s" Q4 F1 h Y' b int Len; int Data[Capacity]; 4 a4 ^& r' Q q6 x2 v xnum() : Len(0) {} 1 o$ c% X4 C& h xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } - |" T9 b1 c- A3 D( A 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]; } ; j) s" T. Z0 V7 K/ I# P: W9 A int operator[](int Index) const { return Data[Index]; } };

; C! N0 X& O1 l2 Iint compare(const xnum& A, const xnum& B) { int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; ) g+ X) R, h# X7 u8 A7 | 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) { " Z. _9 H, K7 U5 g xnum R; 3 C, U2 v$ J) ], |# r+ q int I; ) N) B- ^4 t& {) H. P& | int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) . S! P5 y# u& N3 s9 k% [: }6 |/ | { ( q& @/ l J6 f5 d# A3 [/ u* p4 m* s6 H' \ if (I < A.Len) Carry += A[I]; " E' F, ^. v% O5 ~) i* H- E if (I < B.Len) Carry += B[I]; 0 ]3 T6 r% _9 T; x; e R[I] = Carry % Base; / b- T1 g* e; u. C# n& L Carry /= Base; } 9 |* y- Z% Z+ u4 j- ? R.Len = I; ; Z0 o" h, T P! h8 N return R; }

xnum operator-(const xnum& A, const xnum& B) { + C& W2 }# C! a" `0 U xnum R; int Carry = 0; R.Len = A.Len; int I; for (I = 0; I < R.Len; I++) ( k9 e2 q4 b9 e% u5 ^: s# B$ U { 7 P2 W" o( n% N6 T- J7 N R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; 7 T/ e5 c1 E+ }. ?0 x' A if (R[I] < 0) Carry = 1, R[I] += Base; : w! W. h8 J( H+ Q else Carry = 0; 2 c8 D. f/ y3 n- w8 B# m0 Q. F } : P2 u: k* ~9 v$ q while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; / Y9 o! ?' V$ u, d+ f return R; }

xnum operator*(const xnum& A, const int B) 4 ~. d8 l$ v0 c# D! M' k{ int I; 6 x! q1 `; ^; s5 g1 d5 M# N if (B == 0) return 0; xnum R; P2 p3 P3 k2 ]. g hugeint Carry = 0; , X6 S( a+ b. {0 r: A2 u for (I = 0; I < A.Len || Carry > 0; I++) { if (I < A.Len) Carry += hugeint(A[I]) * B; C: k [) K9 ?/ [5 e2 U3 o R[I] = Carry % Base; Carry /= Base; 1 p- X) ^: _. M+ ^$ ] } & X' R/ u. n d. p" G/ k- B' s R.Len = I; - j2 K/ j T8 B3 ]3 v return R; }

xnum operator*(const xnum& A, const xnum& B) { 9 p; s! O% M! I1 B. } int I; 9 j! ~: f+ d2 i) B; P3 ] if (B.Len == 0) return 0; xnum R; for (I = 0; I < A.Len; I++) { , F7 s" r' j5 H* M hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) + i- c, q" \1 Q% [# R8 `: G4 V { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 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; / p: {, z: ^1 J8 P. p9 ?4 Q Carry /= Base; ! ~6 Y4 j" M( i( [" b } . [: W q' w7 i7 _ } # u; }1 y! m" B+ }( W8 U7 i5 X return R; }

xnum operator/(const xnum& A, const int B) { & t7 E0 f; U1 s9 e8 E; c6 e xnum R; int I; ' e! I' Q, e S3 X7 ^ hugeint C = 0; $ h! }8 `: i4 K- i% _! E" E8 y for (I = A.Len - 1; I >= 0; I--) 1 l" p" o% N% u$ C) y+ c# T; I { C = C * Base + A[I]; $ i: o8 N- V: b$ G J) z, K3 P R[I] = C / B; 1 k5 j3 p2 r: \, c C %= B; } R.Len = A.Len; 5 L. z6 I0 s" [( {: E+ l: m while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 8 j1 [/ k; t- K6 o8 M! C return R; }

xnum operator/(const xnum& A, const xnum& B) { int I; 6 L: a4 _( Z' l8 @8 ~: h' u S xnum R, Carry = 0; # R0 H$ H! x9 H- S p2 e$ @ int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; + J' t' n7 r' c7 \: w6 P. @ Left = 0; Right = Base - 1; while (Left < Right) . j6 B! D( |3 e# i& }4 F { ( L$ q7 x: j+ \2 t% u! d Mid = (Left + Right + 1) / 2; 1 ?' b' J( S6 H2 ]9 u if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; 0 f4 ], R/ i( A } 2 e9 b- K, {+ D* G; K R[I] = Left; 9 a0 K3 X1 X( B: a0 ~ Carry = Carry - B * Left; 4 c" s' ]% n$ `: }' r% Q: N) m } R.Len = A.Len; : o/ B% F; P$ b while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; } 0 j- @( ` l1 E5 D. Fxnum operator%(const xnum& A, const xnum& B) { int I; 5 i& T# ]7 Q+ u xnum R, Carry = 0; 2 l% n# A n$ Q7 P9 e int Left, Right, Mid; ; H/ v- s3 Y' d k for (I = A.Len - 1; I >= 0; I--) 3 B" i$ ?2 @" p& R, y& J { Carry = Carry * Base + A[I]; 5 d/ t: ^8 F! O9 c& d Left = 0; " i; K' Q6 |* t Right = Base - 1; while (Left < Right) & l/ H" g3 m' Z3 {) h) f { 2 Y! D7 r. h8 F Y& Y5 w Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; 4 F, a+ ~4 r6 o# D( x( U# K: I* L else Right = Mid - 1; 1 e7 S1 X% w- e/ w8 u } R[I] = Left; " a# C5 M. d8 t) v3 ?; v Carry = Carry - B * Left; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; % q3 E/ b0 P/ ^0 V3 x1 q; Y' X# C return Carry; }

istream& operator>>(istream& In, xnum& V) % ^8 Z, u+ t- k( s7 |, a{ ) [' ]0 r0 |3 ~% @- k char Ch; 4 f7 p% b* V3 l for (V = 0; In >> Ch;) { V = V * 10 + (Ch - '0'); " _0 r% p X) u: f) f if (cin.peek() <= ' ') break; # x5 X8 l4 y3 ^, W# ]4 v } return In; 4 ~$ Z5 L, s. n* B0 I& l; t}

ostream& operator<<(ostream& Out, const xnum& V) # Y0 N3 \- D# [, ]! G! s{ int I; Out << (V.Len == 0 ? 0 : V[V.Len - 1]); + ^+ A0 c/ A5 V for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; . |2 k) L- P* \9 b- D) D) L return Out; 4 i8 k( c8 y/ i, P# W}

wangjiaqi49

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

cshdzxjtu

强！