POJ1284 Primitive Roots

• wgq615 发布于
• 1597 收藏

题目大意：原根模板题&&欧拉函数模板题，求出模P的原根； 思路：首先根据定理：模m有原根的充要条件：m=1,2,4，p^n，2p^n，其中p是奇素数。 如果模m有原根的话，原根的个数是：φ(φ(m))在此题，p直接给出是奇素数，那就简单了 直接：φ(p-1)撸过去~~就转化成欧拉函数的模板题了      附上理论（来自百度百科）：  原根的定义　　原根Primitive Root。　 　　设m...