11210: 【原1210】原根

题目

题目描述

author: Yanqing Peng 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1210

Description

在数论，特别是整除理论中，原根是一个很重要的概念。

对于不超过\( m \)的\( a \)，在\( gcd(a,m)=1 \)时，定义\( a \)对模\( m \)的指数\( Ord_m(a) \)为使\( a^d \equiv 1 \pmod{m} \)成立的最小的正整数\( d \)。由欧拉定理\( a^{\varphi(m)} \equiv 1 \pmod m \)， \( Ord_m(a) \) 一定小于等于\( \varphi (m) \)。若\( Ord_m (a) = \varphi (m) \)，则称\( a \)是模\( m \)的原根。

Input Format

一个正整数\( m \)

Output Format

以递增序依次输出模\( m \)的所有原根，每行输出一个原根。如果不存在模\( m \)的原根，输出一行-1

Sample Input:

7

Sample Output:

3
5

Hint

设\( m=7 \)，则\( \varphi (m) \)等于\( 6 \)。

设\( a=2 \)，由于\( 2^3 = 8 \equiv 1 \pmod{7} \) ，而\( \displaystyle 3 < 6 \) ，所以\( 2 \)不是模\( 7 \)的一个原根。

设\( a=3 \)，由于\( 3^1 \equiv 3 \pmod{7} \) ， \( 3^2 \equiv 2 \pmod{7} \) ，\(3^3 \equiv 6 \pmod{7} \) ，\(3^4 \equiv 4 \pmod{7} \) ， \( 3^5 \equiv 5 \pmod{7} \)，\( 3^6 \equiv 1 \pmod{7} \) ，因此有\( Ord_7(3) = 6 =\varphi (7) \)，所以\( 3 \)是模\( 7 \)的一个原根。

Limits

对于50%的数据，m<=200

对于100%的数据，m<=10000

Time limit: 1000ms

Memory limit: 65536kb

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！