本文主要是介绍poj 1284 Primitive Roots 【原根】【数论】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接 ： 传送门
题目大意： 求一个质数的原根个数。
先普及一下原根的定义：
设m是正整数，a是整数，若a模m的阶等于euler(m)，则称a为模m的一个原根。
eg: m=7，euler（7） = 6（1，2，3，4，5，6）
则：
- 1 1^(n)mod7=1! = 6
- 2 2^(n)mod7={2 4 1}!=6
- 3 3^(n)mod7={3,2,6,4,5,1}==6 故3是模7的原根
- 4 4^(n)mod7={4,2,1}！=6
- 5 5^(n)mod7={5,4,6,2,3,1}==6 故5是模7的原根
- 6 6^(n)mod7={6,1}！=6
故7的原根有两个。
也可以这样来想： a^(p-1)mod(p)&
这篇关于poj 1284 Primitive Roots 【原根】【数论】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
