Задача А:

Обозначим m = 10¹⁸

Если n > m

рассмотрим отрезки [m * i + 1, min(m * (i + 1), n)]

Рассмотрим отрезок i. Пусть l = m * i + 1, r = min(m * (i + 1), n)

Посчитаем для начала сколько чисел в отрезке имеют нечетное кол-во делителей больше m. Делители числа a больше m могут иметь такой вид a / j, где 1 <  = j <  = i. Пусть тогда b = lcm(1, 2, ..., i). Для каждого j от 0 до (b - 1) посчитаем odd[j]. odd[j] = 1, если кол-во делителей числа j от 1 до i нечетно, иначе odd[j] = 0. Тогда число a имеет нечетное число делителей больше m, если и только если odd[a%b] равно 1. Ну тогда не сложно посчитать кол-во чисел от l до r, у которые нечетное кол-во делителей, это кол-во прибавим к ответу. Осталось в этом отрезке разобраться с квадратами. Если квадрат имеет нечетное кол-во делителей больше m, то лампочка с этим номером не будет гореть, то есть мы что-то лишнее к ответу прибавили. Если же четное, то мы не прибавили еще его к ответу. С квадратами разберемся похожим образом. пусть l' - это минимальное число, что sqr(l') >  = l, а r' - максимальное число, что sqr(r') <  = r. Тогда берем rem от 0 до (b - 1). Посчитаем сколько чисел от l' до r' сравнимы с rem по модулю b. Пусть это будет c чисел, тогда если odd[rem²%b] равно 1, то из ответа вычитаем c, иначе прибавляем.

Я это реализовал за O(9 * lcm(1, 2, ..., 9) * log(lcm(1, 2, ..., 9))) = O(9 * 2520 * log(2520)).