|
高精度,用一个线性表保存一个大整数,具体说,将大整数写成p进制数,线性表的每一项存p进制其中一位。 参考下面代码 #include <iostream>9 M# K8 [0 R/ m9 C
#include <memory># G3 K. z0 A& n7 J1 g; e/ C
# include <string>3 \& \2 @; p" I3 e+ c+ \
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{- H( M, _+ |6 y4 n3 {% j
int Len;& g/ P7 l7 B/ @' ?+ d- C% R% |
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; }' |( K0 G$ W8 u9 V1 ]! m
xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; }0 W7 z- @+ A, T! g
int& operator[](int Index) { return Data[Index]; }! g9 P3 O/ X: X, Y% A/ _" `: w- w
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{* [9 y( C7 ]9 \. K: Q! K
int I;/ J" M0 a& @1 O) T( n
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;8 P: L1 l* b! g' v! c0 l
return A[I] > B[I] ? 1 : -1;! G+ ^+ ^. X: Y: f
} xnum operator+(const xnum& A, const xnum& B)8 n$ R' V2 I. a* d% G B3 o
{ u k/ z# O, J6 \* |7 ~2 E6 K( f
xnum R;
- q5 ^& e' N3 g1 l5 M. p0 |) K$ A int I;
+ T. D* ]: U" F: t' L$ e int Carry = 0;0 y" T2 t1 `3 ?1 f: B( R* S1 e
for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++)
' j; X# q1 z. u {6 ]6 \1 y- }# L0 ]5 p$ M9 D
if (I < A.Len) Carry += A[I];0 I( u8 x. h5 @0 }9 u; {
if (I < B.Len) Carry += B[I];8 R" e' U& Q( Q9 l. ?. L
R[I] = Carry % Base;- P" y9 a+ A9 |1 G+ z% D8 S
Carry /= Base;5 V/ d# E$ D/ Z$ ~, s0 t
}6 I# Q( [% | V, d7 k5 L8 c# M/ V
R.Len = I;" ]$ e3 D3 \2 k
return R;
: m& j" A' c5 K. U} xnum operator-(const xnum& A, const xnum& B)
. c. Y5 u* l( m$ ~# C s6 |{; i! c3 H2 {: |* w0 m
xnum R;1 t$ z6 @+ F" I4 ~
int Carry = 0;) N1 [5 `$ P3 ~* `+ E5 P: l* y/ c
R.Len = A.Len;
& @+ J- h3 T) B int I;3 A$ j {! p) }0 |% ?- B
for (I = 0; I < R.Len; I++)
) @' r# f/ s& o0 y% f7 z {+ F* @# l/ q1 {0 T q" T
R[I] = A[I] - Carry;
2 O1 Y$ v. u+ H7 c) K! j# m if (I < B.Len) R[I] -= B[I];+ {' ~) a) B6 W, r& e; z4 \
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 }- ^/ ]& k* D) W0 B* N9 X1 C
while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--;
1 z: d, @$ c% S return R;2 t* a1 [ H) |! W- h
} xnum operator*(const xnum& A, const int B)
W& e! r2 W: }$ g" r{; c( B& S" ]* U: l
int I;) A) [# a2 H! m* A. o4 O0 ?" c
if (B == 0) return 0;1 Q% J% K1 q. t' R5 G
xnum R;% e3 R$ Z! F7 G/ v& W6 ^! ~
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 {! Q! j( x5 S* I5 E# l. z
if (I < A.Len) Carry += hugeint(A[I]) * B;6 r) g+ q: p7 D5 [
R[I] = Carry % Base;. m: N8 ^1 `& y1 v
Carry /= Base;
7 S9 Z/ R2 S2 y# d }) N, o2 v. l: u3 d# s# ~, e$ v1 N1 L
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;9 Q3 [" S, p0 ^9 B: N9 G: d) a
xnum R;
, l1 N( a8 h* x* v for (I = 0; I < A.Len; I++)
, A2 B) v( L3 \6 \) B {3 c8 I) B1 v$ P4 x ]
hugeint Carry = 0;$ ?& t6 N7 L3 o5 a9 l
for (int J = 0; J < B.Len || Carry > 0; J++); I: ?" Z2 E; ~9 u7 s
{ N, l/ c, Y+ L7 {0 t
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 }+ }0 o; k* `/ T. c" O& a$ m
return R;$ b- M% p( D$ O# k, s( x
} xnum operator/(const xnum& A, const int B)
7 N2 R9 L. Y; {: g* a{7 N# k9 }/ j( k
xnum R;
' L u4 l$ W2 G) V Z% ~ int I;
: _8 Y3 ^- H( w* m- `& H5 p3 Y8 } hugeint C = 0;" W+ [$ s: x% L s; u& s
for (I = A.Len - 1; I >= 0; I--)/ W+ B$ Z* O) A0 E
{7 |: Y. [' m+ i4 ? c! w# E
C = C * Base + A[I];
& V' a) c U4 C2 m& t& Z R[I] = C / B;: B9 K& [# {0 y, j) s
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;' t- q) E; w6 C$ v/ ~, r" v' Q
} xnum operator/(const xnum& A, const xnum& B)
) e7 o3 d1 W/ v6 r" S{: f" U( X8 O8 o
int I;
, @4 e, [* d- _4 j3 s @ xnum R, Carry = 0;) v! E7 x. N, z1 X0 O3 v0 D4 _
int Left, Right, Mid;- U4 [4 {. ]5 o, n
for (I = A.Len - 1; I >= 0; I--)) P- b$ @) m9 ~2 F+ e
{( l, p" \# }$ E. E1 ~: D
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), Q0 T& Q% x; B& Y8 x5 c' c
{, m' z/ D9 L' G: b9 T" \! A
Mid = (Left + Right + 1) / 2;8 _, N/ q1 A7 N- z* Y0 U% S& \5 k; {
if (compare(B * Mid, Carry) <= 0) Left = Mid;/ L4 W. i6 c! J8 N
else Right = Mid - 1;; u- F; E. C% d! U
}
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 }; N9 ?, x1 W! b H ^
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;: b5 T% \! q L* B- d; r
}% G' h. `$ i4 Y" @6 C
xnum operator%(const xnum& A, const xnum& B)
, [( T0 N6 {2 Q( x; }{2 X# X3 z; ]( n- }
int I;6 y, m, {8 n4 p! C
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--)0 m2 V5 q/ e+ W
{! p6 v/ H) A. s$ |9 B
Carry = Carry * Base + A[I];
- ]3 {; K$ R/ v4 {- l0 c$ {& G Left = 0;
! x8 v3 W7 _9 y; B& x Right = Base - 1; j3 U: R7 F9 n; ^! c4 O+ H, b: R5 O
while (Left < Right), b7 G0 @. t, y3 c: R) z
{
' 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;8 X5 R9 f# \& V! z# K/ y: R
}9 d6 ]9 K L2 F: D- Q. H/ E2 u
R[I] = Left;# g4 o2 ]6 j4 G/ c
Carry = Carry - B * Left;0 u% n. w4 W4 a% M/ N
}# g2 `* R8 Q, F
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 Z d% v1 q0 p% T: P3 H
{
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;)7 ]2 N$ O& H* ^) Q6 c7 M+ f
{) w! k) S) t! e: D7 Z
V = V * 10 + (Ch - '0');
, l0 p: ]& y/ X( R if (cin.peek() <= ' ') break;7 G, |. z/ k8 D: o) F
}+ q+ g- z8 N( Z8 S. Q0 u6 |
return In;& o* f! Y( X; m! ]
} ostream& operator<<(ostream& Out, const xnum& V)' y; _& p' j! V {) \, v! m8 y
{
% 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 \ |