stdKonjac's Blog

 要做到不可替代,就要与众不同。

【原根】

题目描述

在数论,特别是整除理论中,原根是一个很重要的概念。
对于不超过 m 的 a ,在 gcd(a,m)=1 时,定义 a 对 m 的指数 Ordm(a) 为使 ad≡1(mod m) 成立的最小的正整数 d 。由欧拉定理,aφ(m) ≡1(mod m),所以Ordm(a)一定小于等于φ(m) 。
若 Ordm(a)= φ(m) ,则称 a 是模 m 的原根。φ(m) 表示 m 的欧拉函数,表示 m 以内与 m 互质的数的个数,特别的,φ(1)=1。

输入格式

输入只有一个正整数 m 。

输出格式

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

样例数据 1

输入

7

输出

3
5

备注

【样例说明】
设m=7,则φ(m)=6 。
设a=2,由于则23 = 8 ≡ 1(mod 7),而 3<6 ,所以2不是模7的一个原根。
设a=3,由于则3≡ 3(mod 7),32 ≡ 2(mod 7),33 ≡ 6(mod 7), 34 ≡ 4(mod 7),35 ≡ 5(mod 7),36 ≡ 1(mod 7),因此有Ord7(3)=6=φ(7),所以3是模7的一个原根。

【数据范围】
50% 的数据,m≤200。
100% 的数据,m≤10000。

一道数学问题……总之先暴力一遍吧φ(m)搞出来,然后分解因数,设k为φ(m)的一个因数,若a≡ 1(mod m) 那a肯定不是m的原根,因为k已经满足条件了并且k比φ(m)小,所以每次都分解然后大暴力就行啦。话说LLX大神告诉我们一个数m的原根个数就是φ(φ(m)),真是吓得我头都掉了……不说了看代码:

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.