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

xuefu998

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

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

[em08][em08][em08]

aftermath

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

参考下面代码

#include <iostream> $ L" c% o9 h# r" d#include <memory> # include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; & `+ |0 x t6 hconst int Capacity = 200;

struct xnum { v. N8 Q$ A$ M: N; S, i1 d) g int Len; 9 H, p, ?0 G4 O$ R1 e int Data[Capacity]; xnum() : Len(0) {} $ i9 o% h- l" l xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } 4 K: m- J4 `# E9 X [1 u6 d: l. H xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } % r. R8 t1 ?- V+ F xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } 8 \/ d1 b! l; \7 k( r- _5 q1 i int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } };

, q u& C* U9 lint compare(const xnum& A, const xnum& B) { 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 z: x4 S0 I8 ]7 U) A) F5 p. { return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) : f8 i$ n1 B: a$ w: v R{ xnum R; int I; 8 F5 e M$ E- O9 N1 a int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; + J- w- A4 s9 s+ [* J- G Carry /= Base; % P8 e2 d( A' i4 A5 _ } R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) { # F! D" V. J) I5 O2 | xnum R; int Carry = 0; R.Len = A.Len; # L3 o* r- Q9 X- v4 A9 V2 Y int I; for (I = 0; I < R.Len; I++) 7 e$ i$ y) _: @$ C { $ D9 Y* y) p9 \5 u |' M8 D# o R[I] = A[I] - Carry; . k# D+ }. G; A6 H: W# F% A. n# a if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; . e) {9 x' N0 V else Carry = 0; } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator*(const xnum& A, const int B) { 1 v3 T% b; q5 r6 { int I; 6 d) D8 Y3 F; l9 v2 g if (B == 0) return 0; xnum R; 7 b9 O% D6 P9 c: n hugeint Carry = 0; for (I = 0; I < A.Len || Carry > 0; I++) 9 @) F; |/ Q/ j5 N* x" p1 p2 e/ H { ) X+ d; K+ Q/ b' k$ s5 Y ] if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; ( M g/ p' ^2 Q8 C$ I Carry /= Base; } R.Len = I; return R; }

xnum operator*(const xnum& A, const xnum& B) { 7 S: F/ c+ [1 C# | k( O int I; if (B.Len == 0) return 0; " d( a% b8 Y( H) Z0 Y' W7 z xnum R; / g5 z. f e3 B0 a8 r- V for (I = 0; I < A.Len; I++) : p4 N3 U. l4 @8 h" O { hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) * [ Q1 r& X* E$ X { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; ! H6 I2 s+ h0 D. \ if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; Carry /= Base; , `" b7 | o2 S0 ?8 U } } return R; ; ^. J. D. g7 ~, G3 O7 C3 v" M: z! r" J}

xnum operator/(const xnum& A, const int B) ( I3 R+ |! d, {/ B# B{ xnum R; # u: H- o& q% N x# {" `0 |0 o int I; hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) 3 L# G& U7 q) x8 t L { C = C * Base + A[I]; R[I] = C / B; & ~# ~$ b. y4 f/ y" ]2 l C %= B; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 9 `. R x n9 ^3 W9 j return R; }

xnum operator/(const xnum& A, const xnum& B) { * m) ` l- p m1 }8 J int I; xnum R, Carry = 0; int Left, Right, Mid; 0 u$ t% [: g4 T( ^0 a0 P- z# w* ] for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; Left = 0; 9 v. l! ?3 ~' `7 U) ?/ I6 U, { Right = Base - 1; while (Left < Right) # X1 s9 j3 S; p5 \4 b { * P% C$ a& ~) s Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; ) F4 w) l* I: g$ O } A. X2 t# K1 ? I) o R[I] = Left; " _2 ]- X( ^, S7 i. @; S Carry = Carry - B * Left; 1 j5 z& b1 Y: z2 J } 0 D4 G6 i# C; ~1 d" _9 d2 A2 g( J R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; - S$ Q s) ?, j1 |5 H5 B s return R; 2 |" e, k* J( `$ `- F) N* }3 z} - }0 _- Q) j6 Z, Z. uxnum operator%(const xnum& A, const xnum& B) { $ B6 g$ @9 |4 `; ^ int I; " I3 `9 w/ A+ U xnum R, Carry = 0; int Left, Right, Mid; P! u6 }& g* h9 ~5 G for (I = A.Len - 1; I >= 0; I--) * G" C+ u+ A; l% | { 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; } 0 Z( Z# w+ S- P4 M8 m R[I] = Left; Carry = Carry - B * Left; d% t, I/ c3 k6 {5 M1 v } R.Len = A.Len; 4 B# ~6 Y; a) z7 e' D. f while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; - ]1 T7 c% Q- E, T% D! U}

istream& operator>>(istream& In, xnum& V) 2 `" K, R! c2 H$ k& L{ char Ch; * v; V8 t' `" p9 A2 r9 r7 I for (V = 0; In >> Ch;) { 8 l8 t* v# c5 g V = V * 10 + (Ch - '0'); / ~" Z3 B+ u ? if (cin.peek() <= ' ') break; } , B) N4 R0 j4 _+ g6 j& Q return In; 2 y* G$ B% U5 w9 m- ?% o0 d+ }}

ostream& operator<<(ostream& Out, const xnum& V) { 6 v# o4 T T1 g) H" m+ n int 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; 1 P ~. v8 d2 e( D/ c' Z/ ]+ G return Out; } ( d9 ^+ t" [/ B8 u, B2 G+ |

wangjiaqi49

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

cshdzxjtu

强！