[Hex0gen]

wk-cof:
Найти число чисел, взаимно простых с N при небольшом числе N - это достаточно простая задача.
Есть, так называемая, Функция Эйлера. Функция Эйлера от числа N численно равна числу чисел меньших N и взаимно простых с N.

Если известно разложение числа N на простые множители, то Функция Эйлера вычисляется за полиномиальное время.

Итак, тебе нужно:
1. Найти разложение числа N на простые множители! Алгоритмов масса (ро-эвристика Полларда, квадратичное решето). Но, поскольку число N - мало (~10^12), то для простоты можно обойтись простым перебором (надо совершить всего ~10^6 делений).

2. Пусть N = (p1^e1)*(p2^e2)*...*(pk^ek), где p1, p2, ... , pk - простые числа.
Число чисел меньших N и взаимно простых с N равно:
F(N) = (p1^e1 - p1^(e1-1))*(p2^e2 - p2^(e2-1))*..*(pk^ek - pk^(ek-1))

Я тут маленькую программку написал, которая вычисляет Функцию Эйлера, если хочешь, коды кину.

Алгоритм вычисления Функции Эйлера прикладываю (: