Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- program GCDs;
- var
- N: Integer;
- T: array [1..100, 1..100] of Integer;
- A, R: array [1..100] of Int64;
- Current: Int64;
- function GCD(A, B: Int64): Int64;
- begin
- if A < B then
- Result := GCD(B, A)
- else
- if B = 0 then
- Result := A
- else
- Result := GCD(B, A mod B);
- end;
- function NOK(A, B: Int64): Int64;
- begin
- Result := (A * B) div GCD(A, B);
- end;
- procedure ReadAndCalc;
- var
- I, J: Integer;
- begin
- Reset(Input, 'input.txt');
- Readln(N);
- for I := 1 to N - 1 do
- begin
- for J := 1 to N - I do
- begin
- Read(T[I, I + J]);
- T[I + J, I] := T[I, I + J];
- end;
- Readln;
- end;
- Close(Input);
- end;
- function Max(A, B: Integer): Integer;
- begin
- if A > B then
- Result := A
- else
- Result := B;
- end;
- procedure GetNextRelativePrime(I: Integer);
- var
- J: Integer;
- Found: Boolean;
- begin
- repeat
- Inc(Current);
- Found := TRUE;
- for J := 1 to I do
- if GCD(Current, R[J]) <> 1 then
- begin
- Found := FALSE;
- break;
- end;
- until Found;
- end;
- procedure GetNext(I: Integer);
- var
- Found: Boolean;
- J: Integer;
- G: Int64;
- begin
- repeat
- Found := TRUE;
- GetNextRelativePrime(I - 1);
- {Теперь нужно предусмотреть, что любая степень простого числа должна встречаться
- в найденном числе меньше раз, чем в НОК всех чисел - просто проверим, что
- заданные ноды не нарушаются}
- for J := 1 to N do
- if I <> J then
- begin
- G := GCD(A[I] * Current, A[J]);
- if G <> T[I, J] then
- begin
- Found := FALSE;
- break;
- end;
- end;
- until Found;
- end;
- procedure Solve;
- var
- I, J: Integer;
- begin
- {Высчитываем начальные значения для A[]}
- for I := 1 to N do
- begin
- A[I] := 1;
- for J := 1 to N do
- if I <> J then
- A[I] := NOK(A[I], T[I, J]);
- end;
- {Начинаем вычислять числа}
- R[1] := 1;
- for I := 2 to N do
- if A[I - 1] >= A[I] then
- begin
- Current := (A[I - 1] + A[I] - 1) div A[I];
- GetNext(I);
- A[I] := A[I] * Current;
- R[I] := Current;
- end
- else
- R[I] := 1;
- end;
- procedure WriteResult;
- var
- I: Integer;
- begin
- Rewrite(Output, 'output.txt');
- for I := 1 to N do
- if I = N then
- Writeln(A[I])
- else
- Write(A[I], ' ');
- Close(Output);
- end;
- begin
- ReadAndCalc;
- Solve;
- WriteResult;
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement