""
, , , . , () , . , ,
30! = 265252859812191058636308480000000?
.
, , "". "" " ".
"" , . "" , , , "" . , , , , .
"" . .
30! = 265252859812191058636308480000000
:
30! = 2 * (104)8 + 6525 * (104)7 + 2859 * (104) + 8121 * (104)5 + 9105 * (104)4 + 8636 * (104)3 + 3084 * (104)2 + 8000 * (104)1 + 0000 * (104)0.
, . 1.
1
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
9 |
0 |
8000 |
3084 |
8636 |
9105 |
8121 |
2859 |
6525 |
2 |
, "" 10000-10 (- , - ), "" .
. 9 [0], " "? , . .
. !
. "" . .
Const MaxDig = 1000; { !}
Osn = 10000; { ,
}
Type Tlong = Array[0..MaxDig] Of Integer;
{ }
"" .
23851674 (Osn) 1000 ( ). ( Ch) . 2.
2
[0] |
[1] |
[2] |
[3] |
Ch |
|
3 |
674 |
851 |
23 |
- |
|
0 |
0 |
0 |
0 |
2 |
|
1 |
2 |
0 |
0 |
3 |
1- |
1 |
23 |
0 |
0 |
8 |
2- |
1 |
238 |
0 |
0 |
5 |
3- |
2 |
385 |
2 |
0 |
1 |
4- : [1] "" [2] |
2 |
851 |
23 |
0 |
6 |
5- |
2 |
516 |
238 |
0 |
7 |
6- |
3 |
167 |
385 |
2 |
4 |
7- |
3 |
674 |
851 |
23 |
( ).
1. [0] () .
2. i i+1, [1]. , " ".
(): . . , A[i] [i+1], .. :
For i := A[0] DownTo 1 Do
Begin
A[i+l] := A[i+l] + (Longint(A[i]) * 10) Div Osn;
A[i] := (LongInt(A[i]) * 10) Mod Osn;
End;
23851674 6 " " . "" "7". "7" [1]. "" . .
i |
[1] |
[2] |
[3] |
ch |
2 |
516 |
238 |
0 |
7 |
2 |
516 |
380 |
2 |
|
1 |
160 |
385 |
2 |
( ch) "" [1] [0].
:
Procedure ReadLong(Var A : Tlong);
Var ch : char; i : Integer;
Begin
FillChar(A, SizeOf(A), 0) ;
Read(ch);
While Not(ch In ['0'..'9']) Do Read(ch);
{ }
While ch In ['0'..'9'] Do
Begin
For i := A[0] DownTo 1 Do
Begin
{"" A[i]
A[i+l]}
A[i+l] := A[i+l] + (LongInt(A[i]) * 10) Div Osn;
A[i] := (LongInt(A[i]) * 10) Mod Osn
End;
A[1] := A[l] + Ord(ch) - Ord('0');
{ [1]}
If A[A[0]+1] > 0 Then Inc(A[0]);
{ , }
Read(ch)
End
End;
. "" .
, . "" , "" , , . . "" 128400583274 :
A[0] |
A[1] |
A[2] |
A[3] |
3 |
3274 |
58 |
1284 |
"" 0058, . , . :
Procedure WriteLong(Const A : Tlong);
Var ls, s : String; i : Integer;
Begin
Str(Osn Div 10, Is);
Write(A[A[0]]; { }
For i := A[0] - l DownTo 1 Do
Begin
Str(A[i], s);
While Length(s) < Length(Is) Do s := '0' + s;
{ }
Write(s)
End;
WriteLn
End;
. , "" .
"", , "" . . SumLongTwo.
"" :
Var A, B, C : Tlong;
Begin
Assign(Input, 'Input.txt'); Reset(Input);
ReadLong(A); ReadLong(B) ;
Close(Input);
SumLongTwo(A, B, C);
Assign(Output, 'Output.txt');
Rewrite(Output);
WriteLong(C);
Close(Output)
End.
. =870613029451, =3475912100517461.
i |
A[i] |
B[i] |
C[1] |
C[2] |
C[3] |
C[4] |
1 |
9451 |
7461 |
6912 |
1 |
0 |
0 |
2 |
1302 |
51 |
6912 |
1354 |
0 |
0 |
3 |
8706 |
9121 |
6912 |
1354 |
7827 |
1 |
4 |
0 |
3475 |
6912 |
1354 |
7827 |
3476 |
, . "" " ".
: = 3476782713546912.
"" .
Procedure SumLongTwo(A, B : Nlong; Var C : Tlong);
Var i, k : Integer;
Begin
FillChar(C, SizeOf (C), 0) ;
If A[0] > B[0] Then k := A[0] Else k : =B[0];
For i := l To k Do
Begin [i+1] := (C[i] + A[i] + B[i]) Div Osn;
C[i] := (C[i] + A[i] + B[i]) Mod Osn
{ ?}
End;
If C[k+l] = 0 Then C[0] := k Else C[0] := k + l
End;
. "" (=, <, >, <=, >=).
Function Eq(A, B : TLong) : Boolean;
Var i : Integer;
Begin
Eq := False;
If A[0] <> B[0] Then Exit
Else Begin
i := l;
While (i <= A[0]) And (A[i] = B[i]) Do Inc(i);
Eq := i = A[0] + l
End
End;
> .
Function More(A, B : Tlong) : Boolean;
Var i : Integer;
Begin If A[0] < B[0] Then More := False
Else If A[0] > B[0] Then More := True
Else Begin
i := A[0];
While (i > 0) And (A[i] = B[i]) Do Dec(i);
If i = 0 Then More := False
Else If A[i] > B[i] Then More := True
Else More:=False
End
End;
Eq More.
Function Less(A, B : Tlong) : Boolean; {A < B}
Begin
Less := Not(More(A, B) Or Eq(A, B))
End;
Function More_Eq(A, B : Tlong) : Boolean; {A >= B}
Begin
More_Eq := More(A, B) Or Eq(A, B)
End;
Function Less_Eq(A, B : Tlong) : Boolean; {A <= B}
Begin
Less_Eq := Not More(A, B)
End;
, , . , 0, , 1, , 2 . . ? . 56784, 634. 2 , , , . . 56700, 567 2 "", . :
Function More(Const , : Tlong; Const sdvig : Integer) : Byte;
Var i : Integer;
Begin
If A[0] > B[0] + sdvig Then More := 0
Else
If A[0] < B[0] + sdvig Then More := l
Else Begin
i := A[0];
While (i > sdvig) And
(A[i] = B[i-sdvig]) Do Dec(i);
If i = sdvig Then Begin
More:=0;
{ }
For i := 1 To sdvig Do
If A[i] > 0 Then Exit;
More := 2;
{ , "" }
End
Else More := Byte(A[i] < B[i-sdvig])
End
End;
. . LongInt.
.
Procedure Mul(Const A : TLong; Const : Longlnt; Var : TLong);
Var i : Integer;
{ - }
Begin
FillChar (, SizeOf(), 0);
If K = 0 Then Inc([0]){ }
Else Begin
For i:= l To A[0] Do
Begin
C[i+l] := (LongInt(A[i]) * K + C[i]) Div Osn;
C[i] := (LongInt(A[i])* K + C[i]) Mod Osn
End;
If C[A[0]+1] > 0 Then C[0]:= A[0] + 1
Else C[0]:= A[0]
{ }
End
End;
.
, , . .
: , , , . "" .
, "" . , 9 11 1 , 10000 9 .
Procedure Sub (Var A : TLong; Const B : TLong; Const sp : Integer);
Var i, j : Integer;
{ sp, }
Begin
For i := l To B[0] Do
Begin Dec(A[i+sp], B[i]);
j: = i;{*}
{ }
while (A[j+sp] < 0) and (j <= A[0]) Do
Begin{*}
Inc(A[j+sp], Osn) ;
Dec(A[j+sp+l]); Inc(j); {*}
end; {*}
{ .
, *,
, ,
,
.
" "}
{If A[i+sp]<0 Then Begin Inc(A[i+sp], Osn);
Dec (A[i+sp+l]);End;}
End;
i := A[0];
While (i > l) And (A[i] = 0) Do Dec(i);
A[0] := i
{ }
End;
, , . 100000001000000000000, 2000073859998.
. , .. .
( ) . :
Procedure Long_Div_Long(Const , : TLong; Var Res, Ost : TLong);
Begin
FillChar(Res, SizeOf(Res), 0); Res[0] := 1;
FillChar(Ost, SizeOf(Ost), 0); 0st[0] := 1;
Case More(A, B, 0) Of
0: MakeDel(A, B, Res, Ost);
{ , , - "" }
1: Ost:=A; { }
2: Res[l] := l; { }
End;
End;
? . . ,
1000143123567 |73859998
- 73859998 |----------
--------- |13541 ( )
261543143
- 221579994
----------
399631495
- 369299990
---------
303315056
- 295439992
----------
78750647
- 73859998
--------
4890649 ()
? (1, 3, 5 ..), , , ... ? , . , . , , "". *10, ( ) . , 564, 63 . , , . Down , Up , Ost .
Down |
Up |
= * ( (Down + Up) Div 2) |
Ost = 564 |
0 |
10 |
315 = 63 * ( (0 + 10) Div 2) |
C < Ost |
5 |
10 |
441 = 63 * ( (5 + 10) Div 2) |
C < Ost |
7 |
10 |
504 = 63 * ( (7 + 10) Div 2) |
C < Ost |
8 |
10 |
567 = 63 * ( (8 + 10) Div 2) |
C > Ost |
8 |
9 |
504 = 63 * ( (8 + 9) Div 2) |
C < Ost |
, (Up + Down) Div 2, Ost . (Down) , () , (Up), .
. 27856, 354. 10, 10000.
Down |
Up |
Ost = 27856 |
|
0 |
10000 |
1770000 |
C > Ost |
0 |
5000 |
885000 |
C > Ost |
0 |
2500 |
442500 |
C > Ost |
0 |
1250 |
221250 |
C > Ost |
0 |
625 |
110448 |
C > Ost |
0 |
312 |
55224 |
C > Ost |
0 |
156 |
27612 |
C < Ost |
78 |
156 |
41418 |
C > Ost |
78 |
117 |
34338 |
C > Ost |
78 |
97 |
30798 |
C > Ost |
78 |
87 |
29028 |
C > Ost |
78 |
82 |
28320 |
C > Ost |
78 |
80 |
27966 |
C > Ost |
78 |
79 |
27612 |
C < Ost |
78, 27856 27612, .. 244.
. "": (More) (Mul) .
Function FindBin(Var Ost : Tlong; Const : TLong; Const sp : Integer) : Longint;
Var Down, Up : Word; C : TLong;
Begin
Down := 0;Up := 0sn;
{ }
While Up - l > Down Do
Begin
{
.
Up>Down. - .}
Mul(, (Up + Down) Div 2, );
Case More(Ost, C, sp) Of
0: Down := (Down + Up) Div 2;
1: Up := (Up + Down) Div 2;
2: Begin Up := (Up + Down) Div 2; Down := Up End;
End;
End;
Mul(B, (Up + Down) Div 2, C);
If More (Ost, C, 0) = 0 Then Sub(Ost, C, sp)
{ }
Else begin Sub (C, Ost, sp); Ost := C end;
FindBin := (Up + Down) Div 2;
{ }
End;
, sp . , , 635 15. ? 63 15 , . . 4, . . 635, 35. . . . 2 5. , ( ) 42, 5. , 10, 10000? , , .
Procedure MakeDel(Const , : TLong; Var Res, Ost : TLong);
Var sp : Integer;
Begin
Ost := A; { }
sp := [0] - [0];
If More(, , sp) = l Then Dec(sp);
{B * Osn > A, }
Res[0] := sp + l;
While sp >= 0 Do
Begin
{ }
Res[sp + 1] := FindBin(Ost, B, sp);
Dec(sp)
End
End;
. : 10-15- , .
1- . , ( 1, 2, 3).
2- . ( 4).
3- . ( 5, 6).
4- . ( 7). , . . , . "" .
1. : "" ; "" ; "" ..
2. "" . ?
3. "" , , . "" .
.. / "" /
http://www.comp-science.narod.ru/
|
|