Работает потому, что мы делаем +1 в индексах по i равных j, 2j, 3j и т.д. вот эти индексы можно формулой посчитать. Ну сколько чисел кратных 10 до 734? Ну ясно же, что 73. Сколько четных до 500? 250. Надо поделить на 2 и округлить вниз.
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, Сначала поймите формулу. Если у вас есть число с простым разложением 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).
wisgest, нету, я что-то не обратил внимание на тег. Но ответ от этого почти не меняется. Суффиксы указывают, когда надо использовать определенный тип в выражении.
Это скорее всего не утечка. Утечка - это когда память постоянно растет. Вы вызываете GdiPlusStartup, он явно что-то выделяет. Нигде GdiplusShutdown соответствующий не вызываете.
А комментарий выше он про набор утилит valgrind, которые включают memory sanitizer, который автоматически ищет утечки памяти. Собираете вашу программу со специальными флагами, запускаете, и она вам в консоли напишет что где и когда утекло. Но тут скорее всего ничего не и найдет.
Что за компилятор вы используете? + не является никакой функцией и этот код не компилируется в C++. Если только у вас там нет каких-нибудь извратов вроде #define + blablabla
Екатерина Воропаева, Даже с учетом, что у вас весьма специфичные строки, похоже чего-то принципиально быстрее обычного квадратичного (по суммарной длине строки) ДП тут нет.
Alexandroppolus, Можно, но это слабо помогает. Там есть только самое примитивное сбалансированное дерево. Если надо считать какую-нибудь сумму в поддереве, то надо писать с нуля что-то (например, декартово дерево). Деревьев отрезков в стандартных библиотеках вообще, по-моему, нет нигде. Их, конечно, можно заменить и балансированным деревом поиска, но только с дополнительными данными по поддеревьям. Но легче писать дерево отрезков, чем декартово дерево, поэтому эту структуру тоже знать надо.
kvellou, Надо примерно понимать, что такое ассимптотическая сложность, почему сортировка слиянием или quicksort работают за O(n log n), почему бинарный поиск за O(log n). Никакие формальные математические доказательства и свойства не нужны. Главное уметь оценить сложность алгоритма.
0xC0000005, Ну вот эти методы вы вызываете у экземпляра Shape при создании. Надо ли вам после передачи их в SFML снова вызывать? По идее - нет. Когда преобразовали к Drawable, больше их не вызываете. Или создайте какой-то совой, класс, который будет наследником Drawable и от которого унаследуете все ваши 5 вещей. Вот в нем можно и GetType реализовать. У себя храните указатели на этот тип. Приводите к Drawable, Только когда передаете в SFML.
Вообще, можно в Drawable определить виртуальный GetType, который для Shape и Text будет возвращать разное, дальше можно в коде проверить этот тип, скастовать указатель к Shape или Text и вызвать уникальные методы (через dynamic_cast. Еще, можно в Drawable объявить виртуальные GetShape и GetText, которые будут возвращать указатель на объект, скастованный к нужному типу). Но это не очень хороший подход. Это значит, что у вас иерархия типов плохо продумана. Надо как можно больше виртуальных методов запихать в Drawable. Какие-то методы будут в наследниках не делать ничего, это нормально. По идее, когда вы ваш Text скастовали к предку Drawable вы должны к этому моменту уже не иметь нужды что-то особо уникальное для текста делать с классом. Вот создали вы Text, заполнили там, допустим, строку. Большее ее менять не придется, Drawable может ничего не знать про текст, но уже можно класс вернуть как Drawable.
Работает потому, что мы делаем +1 в индексах по i равных j, 2j, 3j и т.д. вот эти индексы можно формулой посчитать. Ну сколько чисел кратных 10 до 734? Ну ясно же, что 73. Сколько четных до 500? 250. Надо поделить на 2 и округлить вниз.