POJ 1284 Primitive Roots

• qq_41151162 发布于
• 1215 收藏

题意：给出一个奇素数，求出他的原根的个数，多组数据。 首先何为原根：设mm是正整数，aa是整数，若mm模mm的阶等于ϕ(m)ϕ(m)，则称aa为模mm的一个原根（其中ϕ(m)ϕ(m)表示mm的欧拉函数）。 假设一个数gg对于pp来说是原根，那么gi mod pgi mod p的结果两两不同,且有 1gi mod p≠gj mod pgi mod p≠gj mod p （pp为素数），并且i≠j...