Могу предложить такое решение:

Сгенерируем все делители m. Сделаем бинпоиск по ответу. Переберем a = gcd(i, m) (видим, что a — делитель m), теперь осталось понять, сколько существует таких i = ac и j таких, что Запрос для i сводится к запросу "сколько чисел от 1 до h взаимно просты с m" (где ), ответ на запрос для j просто . Для запроса на i можно применить формулу включения-исключения по простым делителям m. Различных простых делителей не больше 9, поэтому решение работает за . Делителей у числа до 10⁹ может быть порядка тысячи, поэтому такое решение должно заходить.

1) Заметим, что чем больше n, тем больше нулей в таблице. Можем использовать бинарный поиск по ответу.

2) Теперь у нас есть фиксированное n, нужно посчитать количество нулей для него. Зафиксируем номер строчки i, можно увидеть, что ответ для нее — результат целочисленного деления n на величину (m/gcd(m, i)). Нам нужно найти сумму этой величины по всем i.

3) Единственное что меняется в той формуле при смене i — значение gcd(m, i). Давай посчитаем, сколько есть чисел в промежутке 1 до n с фиксированным gcd (различных gcd — ). Зафиксируем очередной делитель m — d[i], для него ответ равен n/d[i], но из этой величины нужно вычесть сумму ответов по всем d[j] таким, что d[j] делится на d[i]. Эту часть, думаю, можно сделать проще принципом включений-исключений, но я не знаю как.

И того, вышло решение за ), это около 30 миллионов на один тест.

UPD: Опередили, но у меня вроде бы немного другое решение

Kostroma, Fcdkbear спасибо :)