Codeforces Round 174 (Div. 2) |
---|
Закончено |
Коровки только что узнали, что такое первообразный корень! Вам дано простое число p, первообразный корень — целое число x (1 ≤ x < p), такое, что ни одно из целых чисел x - 1, x2 - 1, ..., xp - 2 - 1 не делится на p, при этом число xp - 1 - 1 делится на p.
К сожалению, на вычисление первообразных корней уходит много времени, так что коровкам нужна Ваша помощь. Вам дано простое число p, помогите коровкам найти количество первообразных корней .
Во входных данных содержится единственная строка, в которой записано целое число p (2 ≤ p < 2000). Гарантируется, что p является простым числом.
В единственной строке выведите количество первообразных корней .
3
1
5
2
Единственный первообразный корень — 2.
Первообразные корни — 2 и 3.
Название |
---|