301504: CF284A. Cows and Primitive Roots

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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&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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF284A/034cd265b3b5f1590d9fafe2ecd98afd9b39b2a6.png).

输入输出格式

输入格式


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 ![](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. $

Input

题意翻译

## 题目大意 奶牛们刚学会原根的定义!给定一个质数$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$意义下原根个数 ```

加入题单

上一题 下一题 算法标签: