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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF284A/034cd265b3b5f1590d9fafe2ecd98afd9b39b2a6.png) is an integer $ x $ $ (1<=x<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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF284A/034cd265b3b5f1590d9fafe2ecd98afd9b39b2a6.png).
输入输出格式
输入格式
The input contains a single line containing an integer $ p $ $ (2<=p<2000) $ . It is guaranteed that $ p $ is a prime.
输出格式
Output on a single line the number of primitive roots ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF284A/034cd265b3b5f1590d9fafe2ecd98afd9b39b2a6.png).
输入输出样例
输入样例 #1
3
输出样例 #1
1
输入样例 #2
5
输出样例 #2
2
说明
The only primitive root ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF284A/16033b1fae25b830bdfcab89bc221183fb37c884.png) is $ 2. $
The primitive roots ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF284A/87f0d893e5e00cfe20ab5b4b2f1db7bc7a657727.png) are $ 2 $ and $ 3. $