N! делится на P в степени M,но не делится на P в степени M+1.

@Эльман · Регистрация: 04.07.2012

Студворк — интернет-сервис помощи студентам

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

@MayaNash · 09.07.2012, 16:43

решите это пожалуйста, мне интересно как такое решается)

@Puporev · 09.07.2012, 17:24

Лень писать, а принцип такой.
Число р разлагается на простые множители, которые записать в массив, например при р=24
2 2 2 2 3 или 4х2, 3х1
затем от 1 до n все числа также разлагаются на простые множители и создается массив встречаемости каждого числа, например при n=6 будут значения
4х2
3х2
5х1
сейчас нужно пройтись по первому массиву и найти по сколько раз группы множителей есть во втором, найти их кратность. Потом выбрать минимальную, это и будет m.
в данном примере m=1 4/4=1
Может бестолково написал, но как-то так.

@MayaNash · 09.07.2012, 18:15

Puporev, спасибо, знала что надо что-то с разложением на множители, но понятия не имела, что это так делается. спасибо

сейчас сделаю прогу...

@Эльман · 10.07.2012, 01:02 **[ТС]**

решение напиши да по-братски. Надо срочно.

@MayaNash · 10.07.2012, 17:09

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
uses crt;
 
type pointer = ^deliteli;
 
     deliteli = record
     mn,kp,kn: integer;
     next: pointer;
     end;
 
var p,n: integer;
    List: pointer;
 
{---------------------------------------------------------------}
procedure factorP;
var i: integer;
    cur: pointer;
begin
i:=1;
while true do
 begin
 inc(i);
 if p mod i = 0 then
  begin
  new(List);
  List^.mn:=i;
  List^.kp:=1;
  List^.kn:=0;
  p:=p div i;
  while p mod i = 0 do
   begin
   inc(List^.kp);
   p:=p div i;
   end;
  List^.next:=nil;
  break;
  end;
 end;
 
cur:=List;
 
while p > 1 do
 begin
 inc(i);
 if p mod i = 0 then
  begin
  new(cur^.next);
  cur:=cur^.next;
  cur^.mn:=i;
  cur^.kp:=1;
  cur^.kn:=0;
  p:=p div i;
  while p mod i = 0 do
   begin
   inc(cur^.kp);
   p:=p div i;
   end;
  cur^.next:=nil;
  end;
 end;
end;
{---------------------------------------------------------------}
procedure factorN;
var cur: pointer;
    i,nn: integer;
begin
for i:=2 to n do
 begin
 cur:=List;
 nn:=i;
 while (cur <> nil) and (nn > 1) do
  begin
  while nn mod cur^.mn = 0 do
   begin
   inc(cur^.kn);
   nn:=nn div cur^.mn;
   end;
  cur:=cur^.next;
  end;
 end;
end;
{---------------------------------------------------------------}
procedure findM;
var m: integer;
    cur: pointer;
begin
cur:=List;
m:=cur^.kn div cur^.kp;
cur:=cur^.next;
 
while (cur <> nil) and (m > 0) do
 begin
 if cur^.kn div cur^.kp < m then
  m:=cur^.kn div cur^.kp;
 cur:=cur^.next;
 end;
 
writeln('m = ',m);
end;
{---------------------------------------------------------------}
 
 
begin clrscr;
write('p = '); readln(p);
write('n = '); readln(n);
factorP;
factorN;
findM;
readkey; end.

Добавлено через 1 минуту
Puporev, еще раз спасибо) вроде я наконец-то ничего не намудрила)) а то вчера такое писала... сама понять не могла...

Добавлено через 1 час 55 минут
забыла очистить список...

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
uses crt;
 
type pointer = ^deliteli;
 
     deliteli = record
     mn,kp,kn: integer;
     next: pointer;
     end;
 
var p,n: integer;
    List: pointer;
 
{---------------------------------------------------------------}
procedure factorP;
var i: integer;
    cur: pointer;
begin
i:=1;
while true do
 begin
 inc(i);
 if p mod i = 0 then
  begin
  new(List);
  List^.mn:=i;
  List^.kp:=1;
  List^.kn:=0;
  p:=p div i;
  while p mod i = 0 do
   begin
   inc(List^.kp);
   p:=p div i;
   end;
  List^.next:=nil;
  break;
  end;
 end;
 
cur:=List;
 
while p > 1 do
 begin
 inc(i);
 if p mod i = 0 then
  begin
  new(cur^.next);
  cur:=cur^.next;
  cur^.mn:=i;
  cur^.kp:=1;
  cur^.kn:=0;
  p:=p div i;
  while p mod i = 0 do
   begin
   inc(cur^.kp);
   p:=p div i;
   end;
  cur^.next:=nil;
  end;
 end;
end;
{---------------------------------------------------------------}
procedure factorN;
var cur: pointer;
    i,nn: integer;
begin
for i:=2 to n do
 begin
 cur:=List;
 nn:=i;
 while (cur <> nil) and (nn > 1) do
  begin
  while nn mod cur^.mn = 0 do
   begin
   inc(cur^.kn);
   nn:=nn div cur^.mn;
   end;
  cur:=cur^.next;
  end;
 end;
end;
{---------------------------------------------------------------}
procedure findM;
var m: integer;
    cur: pointer;
begin
cur:=List;
m:=cur^.kn div cur^.kp;
cur:=cur^.next;
 
while (cur <> nil) and (m > 0) do
 begin
 if cur^.kn div cur^.kp < m then
  m:=cur^.kn div cur^.kp;
 cur:=cur^.next;
 end;
 
writeln('m = ',m);
end;
{---------------------------------------------------------------}
procedure disposeAll;
var tmp: pointer;
begin
while List <> nil do
 begin
 tmp:=List;
 List:=List^.next;
 dispose(tmp);
 end;
end;
{---------------------------------------------------------------}
 
 
begin clrscr;
write('p = '); readln(p);
write('n = '); readln(n);
factorP;
factorN;
findM;
disposeAll;
readkey; end.

Новые блоги и статьи Все статьи Все блоги /
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .

@Эльман 1 / 1 / 0 Регистрация: 04.07.2012 Сообщений: 21

	N! делится на P в степени M,но не делится на P в степени M+1. 08.07.2012, 20:34. Показов 1104. Ответов 5 Метки нет (Все метки) На входе программе даются два числа N и P. Программа на выходе должна дать такое максимальное число M,что N! делится на P в степени M,но не делится на P в степени M+1. Примечание: 1. Числа N и P так велики,что нет смысла считать значение N!. 2. Числа N и P являются натуральными. 0

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	09.07.2012, 16:43
	решите это пожалуйста, мне интересно как такое решается) 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	09.07.2012, 17:24
	Лень писать, а принцип такой. Число р разлагается на простые множители, которые записать в массив, например при р=24 2 2 2 2 3 или 4х2, 3х1 затем от 1 до n все числа также разлагаются на простые множители и создается массив встречаемости каждого числа, например при n=6 будут значения 4х2 3х2 5х1 сейчас нужно пройтись по первому массиву и найти по сколько раз группы множителей есть во втором, найти их кратность. Потом выбрать минимальную, это и будет m. в данном примере m=1 4/4=1 Может бестолково написал, но как-то так. 2

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	09.07.2012, 18:15
	Puporev, спасибо, знала что надо что-то с разложением на множители, но понятия не имела, что это так делается. спасибо сейчас сделаю прогу... 0

@Эльман 1 / 1 / 0 Регистрация: 04.07.2012 Сообщений: 21
	10.07.2012, 01:02 [ТС]
	решение напиши да по-братски. Надо срочно. 0

N! делится на P в степени M,но не делится на P в степени M+1.

Решение