Пять на Три - Пятнадцать

Проект Эйлер #1 Кратные 3 и 5

Read in English

Текст задачи на  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";
}