Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!