Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу - "Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A". Из года в год и от ученика к ученику меняется только число A. Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу Формат входных данных. Во входном файле содержится единственное число A (1  A  109). Формат выходных данных. В выходной файл вывести единственное число N. Примеры.

input. txt output. txt 8 4 13 13

Имя входного файла input. txt. Имя входного файла output. txt. Максимальное время работы на одном тесте - 2 сек. Максимальное время работы на одном тесте - 2 сек. Максимальный объем используемой памяти 32 мегабайта

Question

Информатика

Рамадан

8 января, 18:18

Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу - "Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A". Из года в год и от ученика к ученику меняется только число A. Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу Формат входных данных. Во входном файле содержится единственное число A (1  A  109). Формат выходных данных. В выходной файл вывести единственное число N. Примеры.

input. txt output. txt 8 4 13 13

Имя входного файла input. txt. Имя входного файла output. txt. Максимальное время работы на одном тесте - 2 сек. Максимальное время работы на одном тесте - 2 сек. Максимальный объем используемой памяти 32 мегабайта

+1

Ответы (1)

Знаете ответ на вопрос?

Фулбрайт · Answer 1

Program Jopascal;

Var

i, A: longint;

x,

u, j,

N, m : longint;

Function FDiv (A, left : LongInt) : LongInt;

var

d,

i : longint;

begin

d : = 1;

for i : = left to Trunc (Sqrt (A)) do

if (A mod i = 0)

then

begin

d : = i;

Break;

end;

if (d 1)

then

FDiv : = d

else

FDiv : = A;

end;

Function g (N, u : longint) : longint;

var

i : longint;

begin

i : = 0;

while (N mod u = 0)

do

begin

Inc (i) ;

N : = N div u;

end;

g : = i;

end;

Begin

Assign (Input, 'input. txt') ;

Assign (Output, 'output. txt') ;

Reset (Input) ;

Read (A) ;

Close (Input) ;

m : = 0;

N : = 1;

i : = FDiv (A, 2) ;

u : = 2;

while (A > 1)

do

begin

N : = N * i;

j : = 0;

while (A mod i = 0)

do

begin

Inc (j) ;

A : = A div i;

end;

if (j > m)

then

begin

m : = j;

u : = i;

end;

i : = FDiv (A, i + 2) ;

end;

x : = 1;

while (g (N * x, u) * N * x < m)

do

Inc (x) ;

N : = N * x;

ReWrite (Output) ;

Write (N) ;

Close (Output) ;

End.