Нужно искать все основания до корня, а потом останутся только системы вида ax+b=n, где х — основание системы численния. Перебираешь а и b, от 3 до 6.

По поводу -1 неправильно — подходят только числа 3-6, а не вообще все, у которых такие цифры. Когда мы смотрим на какое-нибудь 33, то в системе счисления с основанием 100 оно выглядит как одна цифра, аналогичная 33, и нам не подходит :)

Если вычесть из числа его последнюю цифру, то остаток должен делиться на основание системы счисления. Зафиксируем последнюю цифру X, переберем все делители N-X. Поиск делителей втупую за корень у меня таймил, генерация через факторизацию заходит с запасом.

В дорешке зашло решение, где я выбираю ровно одну вершину для первого множества, и проверяю ответ.

Я сделал так, запрос первого типа — стандартное прибавление на дереве отрезков. Запрос второго типа разбил на 2: d < 1000, d >= 1000. Если d < 1000, сделаем С[d] += c. А при при ответе на 3й запрос мы переберем все 1 ≤ d < 1000 и прибавим к ответу (r / С[d] — (l-1) / С[d]). А если d >= 1000, то сделаем N/d прибавлений в дереве отрезков каждый за логарифм. Получается O(MlogN) первый запрос, O(MN / 1000 * logN) второй запрос и O(M(1000 + logN)) третий запрос.

код

Зафиксируем две вершины треугольника — A и B. Возьмем все звезды и черные дыры, которые находятся в верхней полуплоскости относительно прямой, проходящей через А и B, и отстортируем их по полярному углу относительно точки А. Пусть мы рассматриваем некоторую звезду С. Мы хотим знать, содержит ли треугольник АBC черную дыру(обозначим ее Х). Очевидно, что эта черная дыра не может находится позже звезды С в порядке обхода. Если она содержится в треугольнике, то угол ABX должен быть меньше чем угол ABC. Значит, нам достаточно помнить только черную дыру с наименьшим углом ABX, и проверять только ее вхождение. Рассматривая все упорядоченные пары A и B, мы посчитаем каждый хороший треугольник 3 раза. Итого решение за O(n² * (n + m)).

Вместо тысячи слов: оригинал.

1) Допустим условия по стоимости нет. Тогда очевидно нам выгодно идти по деталям в порядке невозрастания A (при равенстве — в порядке невозрастания B) и смотреть, можем ли мы обработать очередную деталь. Если да — нам выгодно ее обрабатывать. Проверять можно следующим образом: отсортируем и детали, и станки так как написано выше, для каждого станка добавляем в мультисет встретившееся значение B, для каждой детали ищем в мультисете наименьшее значение в мультисете, которое больше или равно текущего B. Если нашли — меняем ответ, удаляем значение из мультисеты. Важно при равенстве А сначала смотреть на станки

2) Теперь вернемся к обычной задаче. Посмотрим на функцию цены — она равна 500A+2B. Очевидно, что при данных ограничениях (B<=100) всегда выгоднее использовать детали с большим А (потому что разницу в A при помощи B никак не отыграешь). Значит описанный в пункте 1 алгоритм работает и для обычной задачи.

Осталось не забыть все посчитать в 64-битном типе