Формула включений-исключений
Ошибка.
Попробуйте повторить позже
Найдите сумму натуральных чисел от 
до 
включительно, имеющих с числом 
общие делители, большие
Источники:
Подсказка 1
В условии задачи сказано, что надо просуммировать числа от 1 до 3000, которые не взаимнопросты с 3000. Какие нам тогда числа не подходят, если 3000 = 2³ * 3¹ * 5³?
Подсказка 2
Это значит, что нам подходят числа, которые делятся на 2, или на 3, или 5. Давайте поймём, что если нам подходит число x, то подходит и число 3000-x. При том, все числа, которые подходят под условие выше, разбиваются на пары. Или почти все? А когда тогда посчитать их сумму?
Подсказка 3
Числа 3000 и 1500 не составляют те самые пары, а вот все остальные числа, подходящие под условия все таки разбиваются на пары. Это значит, что нам теперь достаточно найти количество таких чисел и домножить их на 3000 (учтя особую роль в этой сумме исключений выше). Как найти количество таких чисел? Мы ведь не можем просто сложить количество чисел кратных 2, 3 и 5 и получить ответ. У нас есть числа которые кратны сразу двум каким-то, а также числа, кратные сразу всем. Подумайте, как тогда считать их количество?
Подсказка 4
Мы можем посчитать с помощью формулы включений и исключений количество таких чисел, а именно сначала количество просто кратных какому-то, минус сумма кратных сразу двум и плюс сумма кратных всем трём. Получится 2200. Чему тогда равна наша сумма?
, то есть нас интересуют числа, деляющиеся на 
или 
Найдём сначала количество таких чисел. Для этого
воспользуемся принципом включений и исключений. Чётных чисел от 
до 
ровно 
, кратных трём — 
,
кратных пяти — 
. Однако, если просто сложить числа 1500,1000 и 600 , мы посчитаем некоторые числа 2 раза, а именно, числа,
делящиеся на 
и 
, поэтому из полученной суммы надо вычесть 
и 
. Однако,
всё ещё неправильный ответ, Поскольку в этом выражение числа, имеющие все три простых
множителя, сначала считаются три раза, а потом их количество вычитается опять же три раза, поэтому надо снова добавить эти числа.
Количество таких чисел 
, значит, количество чисел, имеющих с 
общие делители и не превосходящих его, это
Заметим теперь, что если какое-то число 
имеет с числом 
общие делители, то число 
тоже имеет с 
те же самые общие
делители. Значит, все интересующие нас числа, кроме чисел 
и 
разбиваются на пары с суммой 
(числу 3000 в пару
пришлось бы сопоставить 
а числу 
само себя). Таких пар получаается 
поэтому итоговый ответ 
Замечание.
Числа, меньшие 
и взаимно простые с ним разбиваются на пары таким же образом, поэтому участники, знакомые с функцией
Эйлера, могли получить формулу для ответа в виде
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
