Wataru

В какой книге написано про nan? По стандарту C++ деление на ноль - это неопределенное поведение:

If the second operand is zero, the behavior is undefined,

Правда, есть одно исключение:

except that if floating-point division is taking place and the type supports IEEE floating-point arithmetic

Вот только этот стандарт IEEE 754 не постулируется стандартом C++ (потому что зависит от аппаратной реализации чисел с плавающей запятой).

Какие-то компиляторы с каким-то уровнем оптимизации могут действительно выдавать nan. Но не все и не всегда.

Есть 2 решения.

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

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

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

Общая сложность у этого решения будет O(n sqrt(a)), но его можно ускорить, если предподсчитать для каждого числа от 1 до A один из его простых делителей.

У вас простой DFS. Если ему не повезет пойти не по отрицательному циклу, но при этом обойти какие-то его вершины, то вы запорите перебор и этот цикл никогда не найдется.

Чтобы через DFS найти отрицательный цикл - придется перебирать ВСЕ циклы. Для этого надо не помечать вершины как visited. Правда, работать будет очень медленно и почти гарантированно не пройдет по time limit, ибо циклов в гарфе может быть экспоненциально много.

Edit, вот вам пример. В графе только один отрицательный цикл 1->2->3->1. Но есть еще ребро 1->3. Если вы начнете из 1-ой вершины, потом возьмете ребро 1->3, то дальше вы из вершины 3 никуда не сможете пойти, уберете ее из стека и пометите как visited. Далее вы рассмотрите ребро 1->2 а потом из вершины 2 ребро 2->3 вы пропустите, потому что вершина 3 уже visited.

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

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

Поскольку 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++ оператор присваивания - это "=". "==" - это оператор сравнения.