Как эффективно получить сумму делителей в заданном диапазоне? - PullRequest
0 голосов
/ 08 января 2019

Я пытаюсь найти сумму всех делителей c в заданном диапазоне a, b a <= b. </p>

Я пытался выполнить цикл от a до b и суммировать все делители c, но это кажется неэффективным, поскольку абсолютная разница между a и b может составлять 10 ^ 9. Есть ли способ, который уменьшает временную сложность этого подхода?

int a, b, c;
cin >> a >> b >> c;
long long sum = 0;
for (int i = a; i <= b; i++) {
    if (i % c == 0) {
       ans += i;
    }
}
cout << sum << endl;

Ответы [ 2 ]

0 голосов
/ 08 января 2019

Определите все простые числа, которые являются делителями c в первую очередь. Это оставит вас со списком чисел [w, x, y, z…]. Затем сохраните набор хеш-таблиц всех кратных чисел в этом списке, которые также являются делителями.

int a, b, c;
cin >> a >> b >> c;
long long sum = 0;

std::vector<int> all_prime_factors = // Get all prime factors of c
std::unordered_set<int> factorSet;
for (int primefactor : all_prime_factors)
{
    int factor = primefactor;
    while (factor <= b)
    {
        if (factor % c == 0)
            factorSet.insert(factor);
        factor += primefactor;
    }
}

for (int x : factorSet)
{
    sum += x;
}

cout << sum << endl;
0 голосов
/ 08 января 2019

Примечание: вопрос неясен, нужно ли нам суммировать делители (в описании) или делимые целые числа (в примере кода). Ответ суммирует делимые пункты.

Это просто.

  • Найти 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';
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...