Математика, опубликовано 2018-08-22 21:25:42 by Гость
Сколько имеется несократимых правильных дробей со знаменателем 123?
Ответ оставил Гость
Правильные дроби – у которых числитель меньше знаменателя.
Со знаменателем 123 таких дробей всего 122, от 1/123 до 122/123.
Несократимые дроби – у которых числитель и знаменатель не имеют общих множителей.
Разложим 123 на множители. 123 = 3*41
Значит, ровно две дроби, 3/123 и 41/123 сокращаются, а остальные 120 дробей – нет.
Ответ: 120.
Не нашли ответа?
Если вы не нашли ответа на свой вопрос, или сомневаетесь в его правильности, то можете воспользоваться формой ниже и уточнить решение. Или воспользуйтесь формой поиска и найдите похожие ответы по предмету Математика.
а) Найдите все несократимые дроби со знаменателем 60, большие
1
3
, но меньшие
1
2
. Сколько таких дробей?
б) Найдите все несократимые дроби с числителем 60, больше
1
3
, но меньшие
1
2
. Сколько таких дробей?
reshalka.com
Математика 5 класс Никольский. Номер №819
Решение а
1
3
=
1
∗
20
3
∗
20
=
20
60
1
2
=
1
∗
30
2
∗
30
=
30
60
Из дробей, заключенных между дробями
20
60
и
30
60
выберем несократимые. Это дроби:
23
60
и
29
60
Ответ:
1
3
<
23
60
,
29
60
<
2
3
Решение б
1
3
=
1
∗
60
3
∗
60
=
60
180
1
2
=
1
∗
60
2
∗
60
=
60
120
У дробей, больших
1
3
с числителем 60, знаменатель должен быть меньше 180, а у дробей, меньших
1
2
с числителем 60, знаменатель должен быть больше 120. Из дробей, заключенных между дробями
60
180
и
60
120
выберем несократимые. Это дроби:
60
179
,
60
173
,
60
169
,
60
167
,
60
163
,
60
161
,
60
157
,
60
151
,
60
149
,
60
143
,
60
139
,
60
137
,
60
133
,
60
131
,
60
127
,
60
121
.
Ответ:
1
3
<
60
179
,
60
173
,
60
169
,
60
167
,
60
163
,
60
161
,
60
157
,
60
151
,
60
149
,
60
143
,
60
139
,
60
137
,
60
133
,
60
131
,
60
127
,
60
121
<
2
3
.
dude78 13 / 13 / 9 Регистрация: 28.07.2017 Сообщений: 103 |
||||
1 |
||||
Количество несократимых дробей на промежутке30.01.2018, 05:01. Показов 4911. Ответов 15 Метки алгоритм евклида, нод (Все метки)
Здравствуйте. Застрял на следующей задаче: Дробь m/ n называется правильной несократимой, если 0 < m < n и НОД (m, n) = 1. Найдите количество правильных несократимых дробей со знаменателем n. Входные данные: Выходные данные: 12 Выходные данные #1 4 Вот код, к этой задаче:
Эта программа очень долго считает. На некотрых тестах истекает лимит времени. Как я понимаю, надо ускорить нахождение НОДа. Подскажите, пожалуйста, как можно улучшить алгоритм Эвклида или идею устранения причыны исчерпания лимита времени…
0 |
Байт Диссидент 27463 / 17152 / 3780 Регистрация: 24.12.2010 Сообщений: 38,631 |
||||
30.01.2018, 11:07 |
2 |
|||
как можно улучшить алгоритм Эвклида Так прям и называется. Улучшенный алгоритм Эвклида Вместо вычитания используется взятие остатка от деления
2 |
║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5 |
|
30.01.2018, 14:05 |
3 |
dude78, забудь о том как находить НОД. Зри в корень. Условие у нас понятно
Найдите количество правильных несократимых дробей со знаменателем n А вот, кое какие мысли
0 < m < n и НОД (m, n) = 1 тогда и только тогда когда факторизация m & n не имеет общих простых отличных от 1. https://ru.wikipedia.org/wiki/… 0%B5%D0%BB Тут вы мне скажете но ведь НОД найти проще чем делать факторизацию всех чисел… и вы будете правы. Но ведь мы не будем все числа разлагать на простые, нам надо знать сколько чисел можно построить с использованием простых которые входят в n и число всех чисел до n. Тогда мы сможем узнать сколько чисел до n не имеют простых множителей сходных с n. Специально написал запутанно, будут вопросы – спрашивайте.
1 |
Диссидент 27463 / 17152 / 3780 Регистрация: 24.12.2010 Сообщений: 38,631 |
|
30.01.2018, 14:19 |
4 |
Сообщение было отмечено dude78 как решение Решениеoutoftime, dude78, фактически тут требуется посчитать функцию Эйлера
1 |
║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5 |
|
30.01.2018, 14:28 |
5 |
Байт, как бы заставить это всё работать за О(1)… Факторизацию надо будет проводить в любом случае… Можно только решетку Эратосфена в памяти держать, чтобы проще было факторизацию делать… Но для 100 тестов и 1 секунды логарифм – то что доктор прописал…
0 |
Байт Диссидент 27463 / 17152 / 3780 Регистрация: 24.12.2010 Сообщений: 38,631 |
||||
30.01.2018, 15:04 |
6 |
|||
как бы заставить это всё работать за О(1) По определения – не получится. О(1) – это конечное время. А тут явно все зависит от величины числа.
Можно только решетку Эратосфена в памяти держать Да, предварительно составленный список простых оченно помог бы делу. Но для достаточно больших n встает вопрос – а где его держать? Добавлено через 3 минуты
Улучшенный Эвклид за логарифм и работает. Тут я слегка соврамши. Логарифм – это для пары чисел. А надо проверять все. Получается в итоге n*log n. Добавлено через 17 минут Однако доказательства того, что не существует решения этой задачи за полиномиальное время, также нет. Просто тупо перебрать все числа до корня из N… Это уже O(sqrt(N))
В хучшем случае (N – простое) N итераций. Добавлено через 2 минуты
1 |
outoftime |
30.01.2018, 15:42
|
Не по теме:
ЗЫ. Я там немного напортачил, но отлизывать сейчас времени нет. Идея, надеюсь, понятна… Если бы только автор понял…
0 |
dude78 13 / 13 / 9 Регистрация: 28.07.2017 Сообщений: 103 |
||||
30.01.2018, 17:59 [ТС] |
8 |
|||
Байт, outoftime,
Но это можно улучшить. Если дошли до p*p > N (Правда, не улучшенная версия, но смысл я вроде понял, так что это поправимо)
Это и есть факторизация. А теперь поинтереснне..
Специально написал запутанно, будут вопросы – спрашивайте. 1) Узнаем количество чисел, которое можно построить с использованием простых чисел, которые входят в n и число всех чисел до n. Вопрос: “которые входят в n и число всех чисел до n”, т.е. нам надо раскладывать каждое число на простые и и находить те, которые еще не встречались и увеличивать счетчик (Это хоть и в лоб, но чтобы было понятно), так? т.е. узнать количество уникальных простых составляющих всех чисел от 1 до n?
1 |
║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5 |
|
30.01.2018, 18:24 |
9 |
.е. узнать количество уникальных простых составляющих всех чисел от 1 до n? Ну у тебя есть факторизация числа. в виде Тогда количество цыфер которые ты можешь с их помощью получить это примерно Короче мне лень сейчас что-либо разъяснять. Читай вики тему факторизации. И да, Байт тебе сразу готовый ответ дал, тебе надо функцию Эйлера считать. Можешь сразу с нее начать и забить на останое что тут говорили, а когда мозги остынут – опять прочитать.
1 |
Диссидент 27463 / 17152 / 3780 Регистрация: 24.12.2010 Сообщений: 38,631 |
|
30.01.2018, 18:36 |
10 |
dude78, В самом деле все проще. Есть функция Эйлера F(n) = количество чисел от 1 до n, взаимно с ним простых. Ссылка в посте 4. Добавлено через 2 минуты Не по теме: В XVIII веке математиков еще можно было понять….:) Добавлено через 5 минут
Тогда количество цыфер которые ты можешь с их помощью получить это примерно Это не совсем так, вернее, совсем не так. Впрочем, точный расчет я только что привел.
1 |
kmqrce 13 / 13 / 5 Регистрация: 18.06.2017 Сообщений: 31 |
||||
30.01.2018, 19:03 |
11 |
|||
Сообщение было отмечено dude78 как решение Решение
2 |
Диссидент 27463 / 17152 / 3780 Регистрация: 24.12.2010 Сообщений: 38,631 |
|
30.01.2018, 19:23 |
12 |
kmqrce, Здорово!
0 |
13 / 13 / 9 Регистрация: 28.07.2017 Сообщений: 103 |
|
30.01.2018, 20:21 [ТС] |
13 |
Байт, тесты прошли, туда пришлось еще несколько изменений внести, чтобы заработал как надо. Думаю, реализацию по Вашей наводке выкладывать не стоит, т.к. в посте 10 и так написаны очень понятные обьяснения . Ребят, спасибо вам! Узнал много нового .
1 |
║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5 |
|
30.01.2018, 20:53 |
14 |
Думаю, реализацию по Вашей наводке выкладывать не стоит Стоит стоит, вот найдет кто-то этот тред и создаст еще один потому что реализации нету. Да и плюс в карму не получишь.
0 |
Диссидент 27463 / 17152 / 3780 Регистрация: 24.12.2010 Сообщений: 38,631 |
|
30.01.2018, 22:46 |
15 |
Да и плюс в карму не получишь Получит, получит…уже получил. Вообще, приятно, что человек работает и осмысляет. И даже “наводки”, не всегда до конца оформленные, мотает себе на ус и творчески использует.
0 |
outoftime |
31.01.2018, 00:00
|
0 |
Сколько имеется несократимых правильных дробей со знаменателем 115? Раскладываем 115 на множители; 115:5=23; 23:23=1; 115=5•23; значит все числа, что делятся на 5 и 23 будут сокращаться; в каждом десятке одна такая дробь будет с 5 и с 23 будет с третьего десятка каждый проще множители посчитать; 23•5=115; с 23; таких 5-1=4; выше (5•23=115 нашли, минус 1, потому что 115будет, это уже не подходит); 23/115; 46/115; 69/115; 92/115;
Считаем всех дробей правильных до 115/115; что на 5 делятся; таких десятков 12; в каждом по 1; и минус последняя 115/115 не берём; 12-1=11дробей; все дроби где 5, они сократятся; 5/115; 15/115; 25/115; 35/115; 45/115; 55/115; 65/115; 75/115; 85/115; 95/115; 105/115; дальше уже 115/115=1 не правильная дробь; и по признаку делимости на 5; все числа заканчиваются на ноль тоже сократятся; таких 11 чисел (10,20… 110); всех дробей не сократимых 115-1-4-11-11=88; ___________ Ответ:88 дробей не сократимых со знаменателем 115;
Дроби делятся на сократимые и несократимые дроби. Рассмотрим подробнее какую дробь называются сократимой и какую дробь называют несократимой.
Сократимая дробь, определение и примеры.
Определение:
Сократимая дробь – это дробь у которой числитель и знаменатель имеют общий положительный делитель не равный нулю и единице.
Например:
Докажите, что дробь (frac{20}{35}) является сократимой.
Решение:
Распишем числитель и знаменатель на простые множители, найдем их наибольший общий делитель (НОД).
20=2⋅2⋅5
35=5⋅7
Так как у числителя и знаменателя повторяется множитель 5, это число и будет их наибольшим общим делителем.
НОД(20, 35)=5
Сократим дробь на НОД.
(frac{20}{35}=frac{4 times 5}{7 times 5}=frac{4}{7})
Из сократимой дроби (frac{20}{35}) получили несократимую дробь (frac{4}{7}).
Несократимая дробь, определение и примеры.
Какие же дроби несократимые или что значит несократимая дробь? Ответ на вопрос кроется в определении.
Определение:
Несократимая дробь – это дробь у которой числитель и знаменатель имеют только один общий делитель равный единице, то есть числитель и знаменатель являются взаимно-простыми числами.
Рассмотрим пример:
Докажите, что дробь (frac{137}{149}) является несократимой дробью.
Решение:
Число 137 является простым, так как оно делиться на 1 и на само себя.
Число 149 является простым, так как оно делиться на 1 и на само себя.
У числителя 137 и знаменателя 149 нет общих делителей, поэтому дробь (frac{137}{149}) является несократимой.
Правило несократимой дроби.
Правило:
- Нужно расписать на простые множители числитель и знаменатель.
- Нужно посмотреть есть ли у числителя и знаменателя общие множители. Если множители есть, то сократить дробь.
- Оставшиеся множители перемножить и записать полученную несократимую дробь.
Пример:
Запишите сократимую дробь в виде несократимой обыкновенной дроби (frac{55}{100}).
Решение:
По правилу несократимой дроби распишем числитель и знаменатель на простые множители.
55=5⋅11
100=5⋅2⋅2⋅5
Видим, что у числителя и знаменателя есть общий множитель равный 5, поэтому сокращаем дробь на 5.
(frac{55}{100}=frac{5 times 11}{5 times 20}=frac{11}{20})
Ответ: получили несократимую дробь (frac{11}{20}).
Неправильные сократимые и несократимые дроби.
Чтобы перевести неправильную сократимую дробь в неправильную несократимую дробь, мы пользуемся теми же правилами, что и для правильной сократимой дроби. Рассмотрим пример:
Запишите неправильную сократимую дробь в виде неправильной несократимой дроби (frac{32}{20}).
Решение:
Разложим числитель и знаменатель на простые множители.
32=2⋅2⋅2⋅2⋅2
20=5⋅2
Общий множитель у числителя и знаменателя равен 2. Распишем
(frac{32}{20}=frac{2 times 2 times 2 times 2 times 2}{5 times 2}=frac{16 times 2}{5 times 2}=frac{16}{5})
Ответ: получили несократимую неправильную дробь (frac{16}{5}).
Вопросы по теме:
Как узнать сократима ли дробь?
Ответ: чтобы узнать сократима ли дробь для начала нужно расписать числитель и знаменатель на простые множители, а потом посмотреть если у них общие множители, если есть, то дробь сократима, иначе – несократима. Рассмотрим пример.
Определите сократима ли дробь (frac{16}{25}).
Решение:
Распишем числитель и знаменатель на простые множители.
16=2⋅2⋅2⋅2
25=5⋅5
Видно, что у числителя и знаменателя нет общих множителей (одинаковых множителей), следовательно, дробь несократима.
Пример:
Сколько несократимых правильных дробей: а) (frac{8}{25}) б) (frac{6}{4}) в) (frac{13}{5}) г) (frac{36}{44}).
Решение:
а) У числителя и знаменателя дроби (frac{8}{25}) (8=2⋅2⋅2, 25=5⋅5) нет общих множителей, поэтому это правильная несократимая дробь. По условию это дробь нам подходит.
б) У числителя и знаменателя дроби (frac{6}{4}) (6=2⋅3, 4=2⋅2, (frac{6}{4}=frac{2 times 3}{2 times 2}=frac{3}{2}) ) есть общий множитель равный 2, поэтому это дробь сократимая и еще неправильная, потому что числитель больше знаменателя. По условию задания эта дробь нам не подходит.
в) Числитель и знаменатель дроби (frac{13}{5}), 5 и 13 простые числа, поэтому общих множителей кроме 1 у них нет, дробь несократимая. Так как числитель больше знаменателя дробь неправильная, поэтому по условию задания нам она не подходит.
г) Числитель и знаменатель дроби (frac{36}{44}) (36=2⋅2⋅3⋅3, 44=2⋅2⋅11) имеют общий множитель равный 4, поэтому дробь (frac{36}{44}=frac{4 times 9}{4 times 11}=frac{9}{11}) является сократимой, правильной. Нам по условию задания не подходит.
Ответ: (frac{8}{25}) несократимая, правильная дробь.
Пример:
Сколько имеется правильных несократимых дробей со знаменателем: а) 145 б) 123 в) 133 г) 115.
Решение:
а) Распишем на простые множители знаменатель 145:
145=5⋅29
Нужно исключить все числа от 1 до 144 кратные 5 и 29.
На 5 делится: 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140.
На 29 делится: 29, 58, 87, 116.
В сумме получаем 32 числа, которые имеют общий множитель с число 145. Всего у нас чисел 144.
144-32=112
Ответ: 112 правильных несократимых дробей со знаменателем 145.
б) Распишем на простые множители знаменатель 123:
123=3⋅41
В диапазоне чисел от 1 до 122 исключаем числа кратные 3 и 41.
На число 3 делится, поэтому не могут находиться в числителе: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120.
На 41 делится: 41, 82.
В сумме получаем 40+2=42 числа, которые имеют общий множитель с число 123, поэтому мы их исключим. Всего у нас чисел 122.
122-42=80
Ответ: 80 правильных несократимых дробей со знаменателем 123.
в) Распишем на простые множители знаменатель 133:
133=7⋅19
Числа от 1 до 132 исключаем, они делятся на 7 и 19, для того чтобы получить все несократимые дроби от (frac{1}{133}) до (frac{132}{133}).
Число 7 кратно: 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126. Всего 18 чисел.
Число 19 кратно:19, 38, 57, 76, 95, 114. Всего 6 чисел.
132-18-6=108
Ответ: 108 правильных несократимых дробей со знаменателем 133.
г) Распишем на простые множители знаменатель 115:
115=5⋅23
Числа от 1 до 114 исключаем.
На 5 делится: 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110. Всего 22 числа.
На 23 делится число: 23, 46, 96, 92. Всего 4 чисел.
114-22-4=88
Ответ: 88 правильных несократимых дробей со знаменателем 115.
Нестандартная задача по математике:
Когда нельзя сокращать сократимую обыкновенную дробь?
Ответ: когда сократимая обыкновенная дробь является номером углового дома или квартала.