Cows and Primitive Roots

题意翻译

## 题目大意 奶牛们刚学会原根的定义!给定一个质数$p$,那么模$p$意义下的一个原根$x(1<=x<p)$满足如下性质:$x-1,x^2-1,x^3-1...x^{p-2}-1$都不能被$p$整除,但是$x^{p-1}-1$却可以 但是奶牛们太菜了需要你的帮助,给定一个质数$p$,求模$p$意义下原根的个数 ## 输入输出格式 ### 输入格式 一个正整数$p(2<=p<=2000)$,保证其为质数 ### 输出格式 模$p$意义下原根个数 ``` ## 题目大意 奶牛们刚学会原根的定义!给定一个质数$p$,那么模$p$意义下的一个原根$x(1<=x<p)$满足如下性质:$x-1,x^2-1,x^3-1...x^{p-2}-1$都不能被$p$整除,但是$x^{p-1}-1$却可以 但是奶牛们太菜了需要你的帮助,给定一个质数$p$,求模$p$意义下原根的个数 ## 输入输出格式 ### 输入格式 一个正整数$p(2<=p<=2000)$,保证其为质数 ### 输出格式 模$p$意义下原根个数 ```

题目描述

The cows have just learned what a primitive root is! Given a prime $ p $ , a primitive root  is an integer $ x $ $ (1<=x&lt;p) $ such that none of integers $ x-1,x^{2}-1,...,x^{p-2}-1 $ are divisible by $ p $ , but $ x^{p-1}-1 $ is. Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime $ p $ , help the cows find the number of primitive roots .

输入输出格式

输入格式

The input contains a single line containing an integer $ p $ $ (2<=p&lt;2000) $ . It is guaranteed that $ p $ is a prime.

输出格式

Output on a single line the number of primitive roots .

输入输出样例

输入样例 #1

3

输出样例 #1

1

输入样例 #2

5

输出样例 #2

2

说明

The only primitive root  is $ 2. $ The primitive roots  are $ 2 $ and $ 3. $