Wataru

Решение у задачи такое должно быть:

Поскольку n^n делится на a, то n делится на все простые делители a. Поэтому надо разложить a на множители (пусть a= p1^k1*p2^k2 ...)

Тогда n надо искать в виде k*p1*p2*...

Это самое k надо перебрать от 1 до максимального ki и проверить, что n^n делится на a. Для этого надо подсчитать, сколько раз k делится на p_i (пусть - это q_i). Тогда надо проверить что, (q_i+1)*n >= k_i для всех простых делителей p_i.

А вдруг непрерывное отображение, которое их связывает, где-то идет вертикально?

Вам надо взять f:[0,1] -> R^2, f(0) = (-1,1), f(1) = (1,-1).

Дальше ввести g(t) = f(t)_y - f(t)_x и там уже применять теорему о промежуточном значении для непрерывных функций.

my_round(123,-2) = 100.

Точность говорит, что все цифры после этого индекса должны быть 0. А предыдущая, может увеличится на 1, в зависимости от правил округления.

Проблема в том, что GCD(0,1000) = 1000. А у вас цикл ни разу не выполнится и не найдет ничего.

Ваше решение не работет, если отрезок вертикальный или горизонтальный. Ответ должен быть 0, вы же выведите что-то другое.

Но, когда вы это исправите, ваше решение скорее всего не пройдет по времени. Ищите наибольший общий делитель алгоритмом евклида.

В с++ разве есть оператор and? Попробуйте заменить sqrt на проверку i*i ==n. Видимо, проблемы с точностью. Плюс может быть переполнение. Сумма должна быть long long.

В c++ оператор присваивания - это "=". "==" - это оператор сравнения.

Вы правильно поняли, какого вида числа будут в последовательности (перемноженные степени 2, 3 и 5).

Проблема в том, что вы, например, пропустите число 2^23, которое входит в первые 10000.

Вам надо поднимать границы от 22, пока сгенерированная последовательность (первые 10000 чисел) не перестанет менятся. Вы сгенерируете первые 10000 чисел точно, и какие-то дальше в последовательности (возможно с пропусками) - всего будет сильно больше 10000 чисел.

Но скорее всего, придется поменять алгоритм. Поскольку ограничения маленькие, то тут можно делать что-то типа BFS. Вы вычисляйте числа в последовательности по порядку. И поддерживайте множество возможных следующих чисел. Каждый раз дописывайте минимальное число из кандидатов к последовательности и добавляйте к кандидатам это новое число, умноженное на 2, на 3 или на 5. Это будет квадратичный алгоритм. Можно использовать heap или какой-нибудь set, тогда будет за O(n log n).

Еще есть линейный алгоритм. Он получается из предыдущего так: все кандидаты разбейте на 3 множества - те, которые получены домножением на 2, на 3 и на 5. Каждое такое множество в итоге будет тупо сама же последовательность, домноженная на 2, 3 или 5. Поэтому единственное, что вам надо знать для полного описания кандидатов - это какое число из последовательности было домножено на 2,3 или 5. Это три индекса.

Т.е. решение будет поддерживать три индекса в уже сгенерированном массиве. Потом смотреть, какое число, домноженное на соответсвующий множитель минимально, это число дописывать в последовательность и этот индекс сдвигать на 1.

Вам придется работать с winapi.

Вам нужно создать прозрачное окно и рисовать в него то, что идет поверх рабочего стола (гуглите "winapi draw in transparent window").

Чтобы не рисовать поверх каких-то окон - надо в каком-то битмапе нарисовать черным цветом силуэты всех этих окон (надо все окна в системе перебрать - тут вам помогут всякие всякие GetWindowRect, EnumWindows, IsWindowVisible.). И при проприсовке надо этот битмап брать как маску (гуглите "winapi clip region").

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

Простой в реализации метод: держите отрезки в каждом элементе отсортированными и непересекающимеся (если два отрезка пересекаются - объедените их).

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

Если же список очень длинный, а ответ ожидается маленький, то есть более быстрый метод. Но он сложный в реализации. Нужно реализовать персистентное дерево поиска. Можно его реализовать на основе персистентного дерева отрезков. Это такая структура, в которую можно добавлять элементы, и удалять их за O(log n). Также можно обходить все элементы за O(log n + (их количество)). Кроме того, сохраняются все версии дерева после каждой операции и общее количество памяти будет O(к log n), где к - количество операций.

Эта структура будет использоватся для хранения предподсчитанных ответов. Если все ваши отрезки нарисовать на одной прямой, то она разобъется на O(n) отрезков, все точки которого будут давать один и тот же ответ при запросе. Мы эти все ответы компактно сохраним.

Используем метод сканирующей прямой. Нанесите все границы всех отрезков на одну прямую, пометив их как начало или конец (и какому элементу списка они соответствуют). Если пройтись по этой прямой слева на право, то будут происходить события - отрезки откроются (новый элемент добавляется в ответ) или отрезки закроются (элемент из ответа удалится). Поддерживая текущий ответ в персистентной структуре мы сильно экономим память. Удобно в качестве начал отрезка брать их координаты, а в качестве конца - координаты концов+1. В таком виде все границы отрезков будут точками, а не числами.

Итак, создайте массив из структур {координата, это начало или конец, номер элемента}. Отсортируйте по координате, потом по флагу начала. Потом пройдитесь по ней и при обработке начала отрезка - добавляйте номер элемента в персистентное дерево. При обработке конца - удаляйте элемент из дерева. Так же перед обработкой каждого элемента запишите в массив-ответ: {предыдущая координата, текущая координата, ссылка на текущую версию персистентного дерева}, если предыдущая координата строго меньше текущей. Этот массив-ответ будет хранить все возможные отрезки с различными наборами ответов в виде {координата начала, координата конца, ответ}.

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

Это решение требует O(n log n) памяти (где n - количество всех отрезков) и O(n log n) времени на предподсчет и O( log n + (ответ)) времени на обработку ответа.

Более простое решение, где ответы считаются так же сканирующей прямой, но сохраняются просто в виде списков, а не версий персистентного дерева, может требовать O(n^2) памяти. Но будет работать быстрее, конечно.

Сначала инвертируйте число (битовое не). Теперь надо найти самый правый единичный бит.
Можно вычесть из числа 1, тогда поменяются все биты вплоть до этого искомого. Значит xor изначального числа и его же минус 1 даст нам столько единичных бит на конце, каков был номер искомого бита.

Дальше надо у этого числа подсчитать количество единичных бит - это тоже известная задача. Сначала представим, что каждый бит хранит сколько в этом бите единичных бит. Потом преобразуем это так, чтобы каждая пара подряд идущих бит хранила двоичное число - сколько единичных бит там было в этом отрезке. Потом каждая четверка бит и в конце все 8 бит. Переход от одного уровня к следующему можно сделать через сумму со сдвигом. Вот код:

// пусть x = 00001011b
x = ~x;  // 11110100b
x = x ^ (x-1);  // 11110100 xor 11110011 = 00000111
x = ((x >> 1) & 01010101b)+(x & 01010101b);  // 00 00 01 10
x = ((x >> 2) & 00110011b)+(x & 00110011b);  // 0000 0011
x = ((x >> 4) & 00001111b)+(x & 00001111b);  // 00000011 = 2
x -= 1; // индексация с 0

Отдельно надо проверить, вдруг изначальное число было 255 - в таком случае искомого бита нет, но этот код вернет 7.

Можно сделать для большего количества бит, надо только еще операций добавить и маски расширить. Для 32-битных чисел надо будет добавить еще 2 операции.

Еще есть вариант с ассемблером в x86 есть операция popcnt.

У вас цикл на 10 итераций (for (int count=0; count < 10; ++count)). С возможным ранним выходом (break).

Что вы подразумеваете под словом "эффективный"?

Проблема в том, что циклов в графе из n вершин может быть O(n!) (n-факториал): представьте клику - граф, где есть ребра между всеми парами вершин. Любое подмножество вершин, да еще и в любом порядке, задает элементарный цикл.

Обычно под словом "эффективный" подразумевают полиномиальный алгоритм. Такой алгоритм тут, очевидно, не существует (потому что надо перебрать экспоненциальное количество объектов).

Используйте обход в глубину без запоминания обойденных вершин. Такой полный перебор гарантированно найдет все циклы. Можно его ускорить, если предварительно разбить граф на двусвязные компоненты мостами и искать циклы внутри каждой компоненты отдельно.

Попробуйте удалить и скомпилировать. Компилятор что говорит?

Константный вектор. Можно вызывать только константные методы, переприсваивать или как-то изменять нельзя.

Но откуда тут вообще может быть непонимание? В C++ никогда нельзя менять, на что ссылаются ссылки. const/не const может быть только то, на что оно ссылается.

Edit: изначально я тут некорректно назвал это константной ссылкой, но по хорошему, оно называется ссылка на константу.