Решение задачи 22.
Найдем простые множители числа P. Пусть это будут p1,..., pK. Для каждого множителя pI найдем число sI - степень, с ко торой pI входит в разложение P на простые сомножители. Как и в задаче 21 найдем максимальные числа m1, ..., mK, такие что N! делится на pI в степени mI, но не делится на pI в степени mI+1.
Получаем для нахождения m следующее уравнение:
,
где R=N!/[(p1m1)*(p2m2)*...*(pkmk)].
Минимальное из чисел mi div si и даст искомую степень M.
Рассмотрим пример:
N=15, P=135.
P=3*3*3*5, p1=3, s1=3, m1=15 div 3 + 15 div (3*3)=6
P2=5, s2=1, m2=3.
Получаем, что M=min{6 div 3, 3 div 1}=2.
Объясните, почему мы не можем применить формулу
M=N div P + N div P2 + N div P3 + ... ?
Приведем полностью программу, реализующую этот алгоритм.
{ Условие задачи.
На входе программе даются два числа N и P. Программа на выходе должна дать такое максимальное число M, что N! делится на P в степени M, но не делится на P в степени M+1.
Примечание.
1. Числа N и P так велики, что нет смысла считать значение N!.
2. Числа N и P являются натуральными.
}
uses crt;
const
max_long = 2147483647;
var
n,p,i,stp,m,mn,km : longint;
flag : boolean;
ch : char;
{ Функция howmany считает, сколько раз в разложении числа n!
присутствует множитель mn.
}
function howmany(mn,n:longint):longint;
var
pr1,pr2,pr3 : longint;
begin
pr1:=mn; pr2:=0; pr3:=1;
while pr3<>0 do
begin
pr3:=trunc(n/pr1);
pr1:=pr1*mn;
pr2:=pr2+pr3
end;
howmany:=pr2
end;
{ Функция st находит степень множителя mn в разложении числа p на простые множители }
function st(mn:longint; var n:longint):longint;
var
prom: longint;
begin
prom:=0;
while (n mod mn)=0 do
begin
inc(prom);
n:=n div mn
end;
st:=prom
end;
begin
clrscr;
while true do
begin
write('Введите число N и P => '); read(n,p); { ввод }
if p<>1 then { если p=1 то число m }
begin { не существует }
m:=max_long;
i:=2;
flag:=true;
repeat
stp:=st(i,p); { stp после присваивания будет равно числу }
if (stp<>0) then { вхождений множителя i в разложении числа p }
begin { на простые множители. Если stp<>0, то km будет равно числу вхождений множителя i }
km:=howmany(i,n);{ в разложении числа n! на простые множители }
if (trunc(km/stp)<m) then { если km/stp меньше минимального отношения, то сохраняем это значение.}
Begin
m:=trunc(km/stp);
if m=0 then flag:=false
end;
end;
if i=2 then i:=3 else inc(i,2);
until (i>p) or (not flag);
writeln('Число M равно ',m)
end
else
writeln('Число M не существует.');
write('Продолжить ? (y/n) ');
repeat
while keypressed do ch:=readkey;
ch:=readkey;
case ch of
'Y','y': writeln('y');
'N','n': begin writeln('n'); exit end
end;
until ch in ['N','n','Y','y'];
end;
end.
{ Описание задачи.
Если взять два любых натуральных числа a и b, то a будет делиться на b, если все степени множителей при разложении числа a на простые множители больше либо равны аналогичных степеней, получаемых при разложении числа b.
Пример :
120 = 2*2*2 * 3 * 5
40 = 2*2*2 * 5
120 делится на 40
Следовательно, n! делится на p в степени m, если степень любого простого число mn (2<=mn<=p) в разложении числа n! на простые множители больше, чем в аналогичном разложении числа p в степени m.
Если F(i,p) - степень простого числа i в разложении числа p на простые множители, то F(i,pm)=F(i,p)*m.
Отсюда алгоритм решения :
Степень m будет равна целой части от минимального отношения степени простого числа i в разложении n! к степени числа i в разложении числа p, где 2<=i<=p.
Алгоритм разложения числа р на простые множители достаточно
прост. Основную трудность представляет алгоритм разложения числа n!.
алгоритм степень_простого_числа_в_разложении_числа_n! (нат n,mn,s,k)
дано n,mn
надо s
нач
s:=0
k:=mn
пока [n/k]>0
нц
s:=s+[n/k]
k:=k*mn
кц
кон.
|
