@leean

Почему мой код не проходит по времени?

Есть задача, решаю на плюсах, суть задачи:
На вход даются два числа, n m
n Нужно найти СУММУ натуральных делителей чисел от n до m;
Тоесть, например:
input: 3 6
output: 11

Код что я написал работает правильно, но на значениях от 1 до 1 000 000 уже идет 12 сек, а дальше и того ложится и не проходит по времени

Если кто знает как еще можно оптимизировать решение, прошу подскажите

Мой код:
#include<bits/stdc++.h>

using namespace std;
set <long long> a;

long long kol=0,kl=0;

void schet(long long n){
    for( long long i=1;i<=sqrt(n);i++){
        if(n%i==0){
            a.insert(i);
            a.insert(n/i);
        }
    }
    kl++;
    kol+=a.size();
    a.clear();

}

int main(){
long long n,m;
cin>>n>>m;
for(long long j=n;j<=m;++j){
schet(j);
}
cout<<kol;

return 0;
}
  • Вопрос задан
  • 365 просмотров
Решения вопроса 2
Adamos
@Adamos
А почему, собственно, 11? Или вам сумму КОЛИЧЕСТВ делителей надо? Судя по коду, да.
Тогда на хрена, собственно, вообще заполнять сет? Что мешает заменить эти вставки простым kol++?

Не говоря уже о том, что задача, полагаю, гораздо эффективнее решается не перебором чисел, а перебором их потенциальных множителей (подсчетом, сколько раз кратные им числа попадут в заданный диапазон).
Ответ написан
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
У вас не самое эффективное решение. Что-то типа O(n sqrt(n)), когда как задачу можно решить за O(n).

Сначала решетом эратосфена найдите для каждого числа минимальный простой делитель. У меня даже статья про этот алгоритм есть с кодом и объяснением.

Потом, решение за O(n log n) - можно быстро найти все простые множители каждого числа используя массив с предущего шага. Считайте степени простых множителей и перемножайте их +1. Так 2^2*3^1 имеет (2+1)(1+1) = 3*2 = 6 делителей (включая 1 и 12. Если они не нужны, вычтите 1-2 в конце).

Но можно сделать еще быстрее. Фактически применив динамическое программирование. Во втором массиве посчитайте степень минимального простого делителя для каждого числа. Если мнимальный делитель (p[i]) для i равен мнимальному для i/p[i], то степень для i будет 1 + степень для i/p[i]. Иначе она будет 1. Так же посчитайте для каждого числа что там останется, если выкинуть все вхождения минимального делителя. Потом в другом массиве посчитайте для каждого числа количество делителей - это ответ для числа без всех вхождений минимального, умноженный на количество этих минимальных делителей +1. Ну а потом по этому массиву считайте сумму. Это будет работать за O(n).
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
А можно для тупых:
Тоесть, например:
input: 3 6
output: 11
3 это 1 * 3 = 4
6 это 1 * 2 * 3 = 6
6+4 = 10
как получить 11 ?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы