原根

定义

am 的阶等于 \phi(m),则称 a 为模 m 的一个原根。
 

求最小原根做法

p-1 = p_1^{k_1} p_2^{k_2} ... p_n^{k_n}, 若 g^{\frac{p-1}{p_i}} \not= 1 (Mod\ p) 恒成立,则 g 为一个模 m 的一个原根。
因为最小的原根往往很小,我们可以去从小到大去穷举这个原根 g, 再去检验它是否是原根,如果不是则接着穷举。所需要的预处理即为将 p-1 分解质因子。分解质因子有必要的话可以线性筛预处理素数。
 

代码

题目链接 51nod
无预处理素数版本:

预处理素数版本:

完结

发表评论

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