: "" - twidler.ru
()
- , - ""
:

""

: ,
:
: 13.01.2014
: 19
:
:
(0)
: 890

""

, , , . , () , . , ,

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/

, : ""
. .
...

,