原根

[Ir1d]

https://oi-wiki.org/math/primitive-root/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛竞赛

[Ame-sora]

貌似前面的（）前面都要带着gcd的吧

[StudyingFather]

@Ame-sora 大多数场合中，可以直接用 (a,b) 表示 gcd(a,b) 的含义。

[Ame-sora]

@StudyingFather
@Ame-sora 大多数场合中，可以直接用 (a,b) 表示 gcd(a,b) 的含义。

哦哦没见过这么写的抱歉

[GeorgePlover]

原根存在定理 的证明的额倒数第二句中的 “$YZ$” 应该是 “$YW$”

[Enter-tainer]

@GeorgePlover 可以来开个pr修复一下吗

[574118090]

阶的性质一似乎有误？要在同余式的两边同时消去 a^j ，应当先保证a和m互素，故条件应当添加a、m互素

[overflowaker]

有习题没？

[hsfzLRX]

最后那个最小原根的数量级，虽然是 $O(m^{0.25})$，但好像在较小的数据上常数较大。看一下这个帖子

[hsfzLRX]

就是这个最小原根可能会大于 $\frac{m}{2}$。

[alexandrelea]

数学公式好像糊了……
图片见链接https://cdn.luogu.com.cn/upload/image_hosting/ug2p0kkq.png