Взаимно простые с числом

Сколько чисел от 1 до $m$ включительно не имеют с числом $n$ общих делителей, кроме единицы?

Одна строка: числа $n$ и $m$ от $1$ до $10^{12}$.

Одно число.

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