Примечание: вопрос неясен, нужно ли нам суммировать делители (в описании) или делимые целые числа (в примере кода). Ответ суммирует делимые пункты.
Это просто.
- Найти
from
, наименьшее значение, такое что from % c == 0 && from >= a
- Найти
to
, наибольшее значение, такое что to % c == 0 && to <= b
.
int n = (to - from) / c + 1;
return n * (to + from) / 2;
Возврат to - from + c
. Позаботьтесь о граничных условиях, когда to
может переполнить ваш тип, а from
может переполниться.
Чтобы найти from
сделайте что-то вроде:
if (c < 0) c *= -1; // works unless c == MIN_INT
if (a % c == 0)
from = a;
else if (a >= 0)
from = (a / c * c) + c
else
from = a / c * c;
Аналогично для to
, но с учетом того факта, что нам нужно округлить, а не увеличивать.
Также, дело с a > b
нужно обрабатывать отдельно.
EDIT
Вот полный код без циклов, рекурсии или контейнеров. Он работает в O (1):
int a, b, c;
std::cin >> a >> b >> c;
if (!std::cin) {
std::cout << "input error\n";
return 0;
}
if (c < 0) c*= -1;
const int from = [a,c] {
// no rounding needed
if (a % c == 0) return a;
// division rounds down to zero
if (a > 0) return (1 + a / c) * c;
// division rounds up to zero
return a / c * c;
}();
const int to = [b,c] {
// no rounding needed
if (b % c == 0) return b;
// division rounds down to zero
if (b > 0) return (b / c) * c;
// division rounds up to zero
return (b / c - 1) * c;
}();
int64_t sum = 0;
if (from <= to)
{
const int n = (to - from) / c + 1;
sum = n * (to + from) / 2;
}
std::cout << sum << '\n';