Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Арифметика >> Номер 23

[Назад]    [Содержание ]    [Вперед]

  


Номер 23


  Условие: Номер 23


Задача22. На входе программе даются два числа N и P. Программа на выходе должна дать такое максимальное число M, что N! делится на P в степени M, но не делится на P в степени M+1. Примечание. 1.Числа N и P так велики , что нет смысла считать значение N!. 2.Числа N и P являются натуральными.

  Решение задачи: Номер 23


Решение задачи 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 кц кон.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017