Исходная постановка задачи
Если мы перечислим все натуральные числа ниже 10, которые кратны 3 или 5 , получаем 3, 5, 6 и 9. Сумма этих кратных чисел равна 23.
Найдите сумму всех кратных 3 или 5 ниже 1000.
Оригинальная ссылка из ProjectEuler.
Общая версия
Найдите сумму всех кратных 3 или 5 под заданным числом N .
Формат ввода:
Первая строка содержит T, количество тестов. за которыми следуют строки T, каждая из которых содержит целое число N.
Ограничения:
1 ≤ N ≤ 10⁹.
Ссылка на версию программы из Hackerrank.
Анализ
Прежде чем прочитать этот раздел, я рекомендую вам сначала подумать о возможном решении ~ 🎀
Простым подходом было бы перейти от 1 к N и суммировать любые кратные 3 или 5, вот простой бонусный код на языке C для этого:
Очевидно, это алгоритм O (N), можем ли мы сделать лучше? Да! O (1) немного лучше.
Начнем с поиска суммы всех кратных 3 ниже N:
(1) Число треугольника также можно выразить в явном формате:
Таким же образом мы определяем сумму, кратную 5 ниже N:
Теперь вы можете подумать, что сумма всех кратных 3 или 5 равна S = S₃ + S₅ , но это неправильно, учитывая, что:
15, 30, ... и все общие числа, кратные 3 и 5 будет суммироваться дважды.
Это можно исправить, вычтя эти общие кратные. Итак, правильным решением будет: S = S₃ + S₅ - (все кратные 3 и 5).
Теперь вопрос в том, как рассчитать эти общие множители?
Любое общее кратное чисел A и B является кратным наименьшему общему кратному
Мы можем получить наименьшее общее кратное, используя приведенную ниже идентичность, затем мы вычисляем сумму повторяющихся чисел,
Тогда правильным решением будет S = S₃ + S₅ - S₁₅
Реализация
- Использование Python
Покажите свою любовь и поддержку, щелкнув в ладоши 👏
