51Nod 1135-原根(快速求解一个素数的原根)

• weiligang512 发布于
• 1509 收藏

题目地址：51Nod 1135 1.原根定义：设m>1,gcd(a,m)=1,使得成立的最小的r，称为a对模m的阶。 2.定理：如果模m有原根，那么他一共有个原根。 3.定理：如果p为素数，那么素数p一定存在原根，并且模p的原根的个数为个。 4.定理：假设m是正整数，a是整数，如果a模m的阶等于，则称a为模m的一个原根。 5.模m有原根的充要条件：m=2,4,P^a,2*P^a……. 求模素数P...