Проект Эйлер #1 Кратные 3 и 5
Текст задачи на HackerRank ProjectEuler+. Задача является версией для программного решения задачи #1 c ProjectEuler.
Дано натуральное число n. Найдите сумму всех натуральных чисел меньше n, делящихся на три или на пять.
Формат ввода
Первая строка содержит число t (1 ≤ t ≤ 10000) - количество тестов. В каждой из следующих t строк содержится число n (1 ≤ n ≤ 10000).
Формат вывода
Для каждого значения n выведите сумму натуральных чисел, меньших n, делящихся на 3 или на 5.
Статус: Полное решение
Просуммируем все числа, кратные трём, и меньшие n, к ним прибавим все числа, кратные пяти, и также меньшие n. Из полученной суммы вычтем числа, делящиеся на пятнадцать, так как мы посчитали их дважды.
Решение
Чтобы каждый раз не перебирать все натуральные числа, меньшие n, в поиске кратных трём или пяти, заметим, что количество чисел, кратных трём, меньших n, в точности равно неполному частному при делении n-1 на 3. Для вычисления суммы достаточно воспользоваться формулой вычисления суммы k первых членов арифметической прогрессии, где k равно (n-1)/3.
Следующий код вычислет сумму для тройки:
Следующий код вычислет сумму для тройки:
int k = (n-1)/3; sum = ((3 + k*3)*k)/2;или
int k = (n-1)/3; sum = 3*(k+1)*k/2;
Осталось добавить аналогичные строки для 5 и 15, и не забыть о возможном переполнении. Окончательный код:
int t, n, c; cin >> t; long long sum; for (int i = 0; i < t; ++i) { cin >> n; sum = 0; n--; c = n/3; sum += 3ll*(c+1)*c/2; c = n/5; sum += 5ll*(c+1)*c/2; c = n/15; sum -= 15ll*(c+1)*c/2; cout << sum << "\n"; }
Комментариев нет:
Отправить комментарий