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

Question

[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;
}

Answer 1

[Adamos]

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

Не говоря уже о том, что задача, полагаю, гораздо эффективнее решается не перебором чисел, а перебором их потенциальных множителей (подсчетом, сколько раз кратные им числа попадут в заданный диапазон).

Comments

[Lynn «Кофеман»]

Насколько я понял 11 получается так:
3 — 1 (только один делитель меньше 3, и кстати есть всегда, так что его можно не считать отдельно и в конце просто прибавить количество чисел)
4 — 1 + 2
5 — 1
6 — 1 +2 + 3
итого: (1) + (1 + 2) + (1) + (1 + 2 + 3) = 11.

[leean]

Lynn «Кофеман», да, все так

[leean]

очевидно сет нужен для того что число 16 например, делится на 4 и в ответе даёт 4, поэтому мне нжуен сет который не заносит одно и тоже числа 2жды

[Adamos]

Lynn «Кофеман», в делители в математике включается и 1, и само число.
У ТС в коде, собственно, выводится только количество, я плясал от этого.
И в коде же само число заносится в сет (при i = 1)

[leean]

Adamos, да правильно, подходит в решение не только 3 по 1, а так же 1 по 3, это будет считаться за 2 разных решения и само сабой за 2 разных делителя

[Adamos]

leean, может, для начала определиться, что ты вообще считаешь? Твой код считает и выводит количество делителей. Хотя в задаче (если она передана без купюр) - сумма.

[leean]

Adamos, нет, я передавал своими словами, и как я там же написал мой код уже все считает ВЕРНО, но не проходит по времени, я написал тут вопрос чтобы кто-то возможно смог мне подсказать как можно переписать это решение другим методом или же исправить мой код

[Adamos]

leean, ну, и про "не только 3 по 1, а так же 1 по 3" ты тоже врешь. Код-то читал хотя бы?

[Adamos]

leean, про другой метод - см. вторую половину моего ответа.

[leean]

Adamos, что, я же сказал что заносится оба и 3 и 1, у меня оба и заносятся и считаются за 2 разных делителя

[leean]

Adamos, я хотел уточнить что конкретно ты имел ввиду, может есть где почитать про то что ты описал, я не понял немного с твоих слов

[Adamos]

leean, заносятся - два, как есть.
Только никакого переворачивания 1 * 3 в 3 * 1 (цитирую: "это будет считаться за 2 разных решения") там нет.

[leean]

Adamos, мне не нужно по задаче куда-то что-то вставлять в каком-то порядке, все что меня интересует это сколько разных чисел я занес в set после прохода от 1 до корня n, это и есть кол-во делителей

[Adamos]

leean, я конкретно имел в виду один цикл от 1 до корня из большего числа, для каждого числа в этом цикле проверяется (точнее - вычисляется по элементарно выводимой формуле), сколько в указанном диапазоне кратных ему чисел. Можно начать на простых числах на бумажке, закономерность очевидна.

[leean]

Adamos, ты имеешь ввиду что у кратных чисел условному числу 12 одинаковое кол-во делителей, или как? не пойму еще от 1 ты идешь типо до 6 если вводы был 3 6

[Adamos]

leean, берешь бумажку и считаешь, сколько раз в диапазоне от 5 до 12 встречаются числа, кратные 1.
Потом - 2.
Потом - 3.
Если просветление не наступает, берешь диапазон побольше...

[leean]

Adamos, пока не понимаю как то что ты написал можно применить к промежутку так что бы это еще и по времени проходило, 2 фора работают до 10 в 4й, а как сделать за 1 не пойму

[Adamos]

leean, бумажку. И диапазон от 5 до 36.
Подскажу: на 1 делятся 32 числа, на 2 - 16. Но это просто совпадение.
Кратные 3, 4, 5 и 6 посчитай сам. Сначала - на пальцах, потом, когда дойдет - по формуле.
Вот эта формула в цикле - все, что нужно для решения этой задачи.

[leean]

Adamos, честно я все выписал, не понимаю чего-то простого похоже, ну есть смысл в том чтобделить например на простые числа, но опять же когда у тебя промежутк от 1 до 100000000 нуно пройти по кажому числу.
Я подумал следующие
Каждое числа минимум имеет по 1 делителю 1
Каждое второк уже имеет делитель 2
Каждое 3е имеет дилитель 3
Каждое 5е имеет делитель 5
Но я все равно не пойму как тут в 1 пробег уместить деление на все простые числа.
Еще пришла в голову идея найти все простые числа в промежутке от 1го до m(большее из 2х чисел)
и поделить кол-во чисел от n до m на все простые числа, но опять же ответ не правильный получается

[Adamos]

leean, вообще-то тут простота никакой роли и не играет.
Это то же самое решето Эратосфена по диапазону, только с подсчетом выбиваемых ячеек.
После которого больше уже и считать нечего, потому что в задаче только это и требуется.

Кстати, в рассуждениях ошибка: не "каждое второе", а "каждое четное".
В диапазоне от n до m нужно найти крайние числа внутри диапазона, кратные k:
M = m - m % k;
N = n + (k - n % k) % k; // может, можно и проще, но сойдет и так
sum = (M - N) / k + 1; // количество чисел, кратных k, в заданном диапазоне.
Каждое из них дает по 2 делителя так же, как в приведенном в вопросе коде (кроме квадрата, дающего два одинаковых делителя - так что удваиваем результат, но если квадрат k лежит в нужном диапазоне - уменьшаем его на 1).
Складываем эти результаты в цикле от 1 до корня из m - получаем нужный итог.

[leean]

Adamos,

int main(){
long long M,N,n,m,kol,sum=0;
cin>>n>>m;
resheto(m); // после этого в b массиве у меня лежат все простые числа от 2 до m
for(int i=0;i<b.size();++i){
    M = m - m % b[i];
    N = n + (b[i] - n % b[i]) % b[i];
    int sum1;
    sum1 = (M - N) / b[i] + 1;
    sum1=sum1*2;
    sum+=sum1;

}
    cout<<sum;
return 0;
}

Я что-то не так понял похоже

[Adamos]

leean, вы комбинируете два ответа в кучу.
В моем варианте вам нужно просто перебрать все числа. Не только простые. И не выстраивая предварительно решето.

[leean]

Adamos, ой да простите брейн лаг, я читал сначала объяснение от вас, потом от другого человека
вот код который я написал как вы и сказали вроде бы, да он проходит уже больше но ложится на предельных значениях
например
1863645378 2000773105
правильный ответ на этот тест: 3090331815
но он виснет

#include<bits/stdc++.h>

using namespace std;
int main(){
unsigned long long M,N,n,m,kol,sum=0;
cin>>n>>m;

for(unsigned long long i=1;i<m;++i){
    M = m - m % i;
    N = n + (i - n % i) % i;
    unsigned long long sum1;
    sum1 = (M - N) / i + 1;
    sum+=sum1;

}
    cout<<sum+1;
return 0;
}

[Adamos]

leean, корень из m же.
Но учесть, что каждый раз получается два множителя, кроме случаев n <= i*i <= m.

[Adamos]

leean, квадраты можно учесть после, просто посчитав, сколько в диапазоне квадратов (логика аналогична).

[leean]

Adamos, отет получается не рпавильный, если умножаю на 2 тоже не правильый, я что-то не учитываю, похоже то что при делении делитель и ответ могут быть одинаковые

[Adamos]

leean, похоже, оба ответа таки сошлись в один, вам осталось немножко поработать напильником - удвоить результат и вычесть кол-во квадратов в диапазоне.

[leean]

Adamos, вот что такое "кол-во вадратов" я вообще не доганяю, вы имеете ввиду чесил из которых можно извлеч корень или что под этим подрузомивается?

[Adamos]

leean, числа, являющиеся квадратом другого числа, очевидно.
У них этот алгоритм при удвоении результата будет давать один лишний множитель, его нужно вычесть.

Answer 2

[Wataru]

У вас не самое эффективное решение. Что-то типа 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).

Comments

[leean]

честно говоря слегка запутонное объяснение, я понял для чего вы используете решето эртосфена но не понял что вы делаете дальше по вашему способу за 0(n log n), про диномическое тоже слегка запутанно, сложно понять что вы имеете ввиду за 2 массива и чем я должен их заполнить. Все равно спасибо за ответ, скорее всего я попробую решить первм способом с помощью решета но не пойму часть с перемножением степеней на +1

[Wataru]

leean, Сначала поймите формулу. Если у вас есть число с простым разложением p1^k1 p2^k2 p3^k3...pn^kn, то у него (k1+1)(k2+1)..(kn+1) делителей (всех, не только простых). Ну, потому что p1 можно брать в степени от 0 до k1. Независимо от этого можно от 0 до k2 раз взять p2 и так далее. Например, 12= 2^2*3 имеет (2+1)(1+1) = 6 делителей: 1, 2, 3, 4, 6, 12.

Далее, вот решетом эратосфена вы нашли для кажого числа его минимальный простой делитель. Вот теперь можно разложить любое число на его простые делители за log(n) (а не sqrt(n), как у вас) операций. Вот есть у вас 12. Вы уже знаете, что его минимальный простой делитель равен 2 (из эратосфена). Записали 2, поделили на него. Осталось 6. Для него вы уже знаете делитель 2. Записали, поделили, осталось 3. Для него вы знаете делитель 3. Итого вы нашли делители {2,2,3} осталось найти количества повторений. Более того, делители вы получаете в порядке возрастания, так что они уже идут группами.

Но на самом деле я перемудрил. В этой задаче можно проще: не считайте для каждого числа из отрезка, сколько у него делителей. А считайте для каждого делителя, сколько чисел в отрезке оно делит. Это легко подсчитать, если у вас отрезок от 1 до n. Число x там входит ровно в floor(n/x) чисел. Для отрезка [a,b] вычтите результат для [1,a-1] из [1,b]. Просуммируйте по всем возможным делителям (до b).

[leean]

Wataru, по поводу 2х первых обзацев, спасибо за разъяснение я все понял теперь
а по поводу второго, вот вы говорить взять floor(n/x) и найти кол-во чисел от 1 до n делится на x, а что брать за x? откуда брать числа на которые я буду делить и до каких пор я это буду делать? Тобишь понятно что все делители числа будут расположены 100% до или включительно корня из n, тоесть все делители для 100 будут расположены ниже 10 включительно, но каким образом делить именно на те числа которые нужны чтобы алгоритм работал быстрее?

[Wataru]

leean, этот x надо перебрать. от 1 до правой границы. Вы же в своем решении перебираете все делители числа от 1. Вот это решение это как бы развернув циклы.

У вас было

for n = a .. b:
   for divisor = 1.. n
     if n % divisor == 0: ++ans

В быстром решении мы просто меняем местами 2 внешних цикла:

for divisor = 1.. n: 
   for n = a .. b: 
     if n % divisor == 0: ++ans

Ну и потом схлопываем внутренний цикл в 2 деления с вычитанием используя элементарную математику.

[leean]

Wataru, написал как вы ссказали 1 в 1, и я не пойму почему это решение должно работать быстрее, оно медленнее чем мое, вот код что я накалякал по вашим замечаниям:

#include<bits/stdc++.h>

using namespace std;
set <long long> a;

long long kol=0,kl=0;



int main(){
long long n,m;
cin>>n>>m;
for(long long j=1;j<=m;++j){
    for(long long i=n;i<=m;i++){
            if(i%j==0){
                kol++;
            }
        }
}
cout<<kol;

return 0;
}

[leean]

leean, решение то рабочие, и написано куда легче чем мое да, но скорости не прибавило, по хорошему нужно обойтись 1 фором чтоб уложится в 1 секунду

[Wataru]

leean, анутренний for заменяется на формулу. Что-то вроде m/j-(n-1)/j.

[leean]

Wataru, этого вообще не понял, как это написать не складывается в голове

[Wataru]

leean, ну просто kol += n/j...

[leean]

Wataru, спасибо, ваше решение работает на последнем тесте за 7 секунд, я чесно говоря очень слабо понял формулу и до сих пор не знаю почему это работает, а так же я понимаю что можно ускорить дописав до sqrt(m) а не до m но получается не правильный овтет и случай в котором это можно пофиксить, я не понимаю как это записать

int main(){
long long n,m;
cin>>n>>m;
for(long long j=1;j<=sqrt(m);++j){
        kol+= m/j-(n-1)/j;

}
cout<<kol;

return 0;
}

[Wataru]

leean, нет, тут нельзя ускорить до sqrt.

Работает потому, что мы делаем +1 в индексах по i равных j, 2j, 3j и т.д. вот эти индексы можно формулой посчитать. Ну сколько чисел кратных 10 до 734? Ну ясно же, что 73. Сколько четных до 500? 250. Надо поделить на 2 и округлить вниз.

[leean]

Wataru, тобишь идти до floor(m+1/2)

[Wataru]

leean, Вообще, да, можно сократить до m/2 потому что все итерации после дадут ровно 1 всегда и их можно в одно действие подсчитать. И как, все еще не проходит? Какие там вообще ограничения в задаче на размер чисел и time limit?

[leean]

Wataru, вообще ограничения 1<=n<=m<=10 в 9 степени
Время: 1 сек
Вроде прошло, но увы некуда отправить, задача из старой олимпиады и та на английском языке, есть только тесты которых 20, ниже в коментариях приводил пример человеку

[Wataru]

leean, А вообще, я был не прав. Можно и до корня сократить же.

Рассмотрим сумму floor(m/i) для i до корня ее просто подсчитаем. Для оставшихся слагаемых, когда i >= корня, будем считать сколько раз каждое слагаемое всречается. при i >= sqrt(m), j = m/i <= sqrt(m). Вот переберем это j. Для скольких i можно получить floor(m/i) = j? j <= m/i < j+1, m/(j+1) < i <= m/j, отсюда i = floor(m/(j+1))+1 .. floor(m/j). В итоге, надо подсчитать сумму floor(m/j) - floor(m/(j+1)).

в итоге будет что-то вроде

for(long long j=1;j<sqrt(m);++j){
        kol += 2*(m/j) - m/(j+1) ;
}
for(long long j=1;j<sqrt(n-1);++j){
        kol -= 2*((n-1)/j) - (n-1)/(j+1) ;
}

Возможно накосячил и где то +-1 надо. Особенно аккуратно проверьте, что работает, когда m и/или n - полный квадрат.

[Wataru]

leean, Если числа до 10^9, то наверно надо за корень делать.

[leean]

Wataru, Обязательно попробую но тут ты уюе намудрил кнч, я честно ваще не понимаю к чему ты тут клонишь и что имеешь ввиду, но думаю той формулы бы хватило на полный бал, хотя это скорее всего полное решение до корня, разобраться бы и понять что и как тут работает

[Wataru]

leean, Ну поэтапно же все познается. Формулуkol+= m/j-(n-1)/j то понял? Дальше разбиваем на 2 отдельные суммы. Одну с m, другую с n-1.

Дальше, слагаемые с j до корня считаем просто тупо циклом. А оставшиеся слагаемые группируем. Это тот же прием, что и в самом начале сделали. Вместо счета суммы чисел, считаем, а сколько раз каждое число в сумме участвует.

И я там накосячил, надо же "сколько раз число в сумме" домножить на само число. Что-то вроде должно быть
kol += (m/j) +j*(m/j- m/(j+1)) ;

Answer 3

[Алексей Копендаков]

А можно для тупых:
Тоесть, например:
input: 3 6
output: 11
3 это 1 * 3 = 4
6 это 1 * 2 * 3 = 6
6+4 = 10
как получить 11 ?