Advertisement
Guest User

Untitled

a guest
May 28th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Delphi 2.60 KB | None | 0 0
  1. program GCDs;
  2.  
  3. var
  4.   N: Integer;
  5.   T: array [1..100, 1..100] of Integer;
  6.   A, R: array [1..100] of Int64;
  7.   Current: Int64;
  8.  
  9. function GCD(A, B: Int64): Int64;
  10. begin
  11.   if A < B then
  12.     Result := GCD(B, A)
  13.   else
  14.     if B = 0 then
  15.       Result := A
  16.     else
  17.       Result := GCD(B, A mod B);
  18. end;
  19.  
  20. function NOK(A, B: Int64): Int64;
  21. begin
  22.   Result := (A * B) div GCD(A, B);
  23. end;
  24.  
  25. procedure ReadAndCalc;
  26. var
  27.   I, J: Integer;
  28. begin
  29.   Reset(Input, 'input.txt');
  30.   Readln(N);
  31.   for I := 1 to N - 1 do
  32.   begin
  33.     for J := 1 to N - I do
  34.     begin
  35.       Read(T[I, I + J]);
  36.       T[I + J, I] := T[I, I + J];
  37.     end;
  38.     Readln;
  39.   end;
  40.   Close(Input);
  41. end;
  42.  
  43. function Max(A, B: Integer): Integer;
  44. begin
  45.   if A > B then
  46.     Result := A
  47.   else
  48.     Result := B;  
  49. end;
  50.  
  51. procedure GetNextRelativePrime(I: Integer);
  52. var
  53.   J: Integer;
  54.   Found: Boolean;
  55. begin
  56.   repeat
  57.     Inc(Current);
  58.     Found := TRUE;
  59.     for J := 1 to I do
  60.       if GCD(Current, R[J]) <> 1 then
  61.       begin
  62.         Found := FALSE;
  63.         break;
  64.       end;
  65.   until Found;
  66. end;
  67.  
  68. procedure GetNext(I: Integer);
  69. var
  70.   Found: Boolean;
  71.   J: Integer;
  72.   G: Int64;
  73. begin
  74.   repeat
  75.     Found := TRUE;
  76.     GetNextRelativePrime(I - 1);
  77.     {Теперь нужно предусмотреть, что любая степень простого числа должна встречаться
  78.      в найденном числе меньше раз, чем в НОК всех чисел - просто проверим, что
  79.      заданные ноды не нарушаются}
  80.     for J := 1 to N do
  81.       if I <> J then
  82.       begin
  83.         G := GCD(A[I] * Current, A[J]);
  84.         if G <> T[I, J] then
  85.         begin
  86.           Found := FALSE;
  87.           break;
  88.         end;
  89.       end;
  90.   until Found;
  91. end;
  92.  
  93. procedure Solve;
  94. var
  95.   I, J: Integer;
  96. begin
  97.   {Высчитываем начальные значения для A[]}
  98.   for I := 1 to N do
  99.   begin
  100.     A[I] := 1;
  101.     for J := 1 to N do
  102.       if I <> J then
  103.         A[I] := NOK(A[I], T[I, J]);
  104.   end;
  105.   {Начинаем вычислять числа}
  106.   R[1] := 1;
  107.   for I := 2 to N do
  108.     if A[I - 1] >= A[I] then
  109.     begin
  110.       Current := (A[I - 1] + A[I] - 1) div A[I];
  111.       GetNext(I);
  112.       A[I] := A[I] * Current;
  113.       R[I] := Current;
  114.     end
  115.     else
  116.       R[I] := 1;
  117. end;
  118.  
  119. procedure WriteResult;
  120. var
  121.   I: Integer;
  122. begin
  123.   Rewrite(Output, 'output.txt');
  124.   for I := 1 to N do
  125.     if I = N then
  126.       Writeln(A[I])
  127.     else
  128.       Write(A[I], ' ');  
  129.   Close(Output);
  130. end;
  131.  
  132. begin
  133.   ReadAndCalc;
  134.   Solve;
  135.   WriteResult;
  136. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement