HDU4992 求所有原根

2024-01-27 11:40| 来源: 网络整理| 查看: 265

有原根的数只有2,4,p^n,2p^n(p为质数,n为正整数)。一个数的最小原根的大小是O(n0.25)的。如果g为n的原根，则gd为n的原根的充要条件是(d,φ(n))=1；如果n有原根，它的原根个数为φ(φ(n))。

那么来看一下这道题：

首先根据性质1，我们可以通过预处理质数，把不存在的情况判掉。

然后根据性质3，找到一个原根后枚举次方判gcd就可以了。

怎么找到一个原根呢？按照性质2傻傻去跑在这种多组数据的题目里是肯定不行的。

那么有一个喜大普奔的结论来帮助我们：

因为gφ(n)≡1(mod n)，而对于比φ(n)小的数都不成立。

枚举φ(n)的质因子p，看gφ(n)/p在模意义下是否是1。

是1的话g就不是原根。

证明起来有点麻烦，这里就不写了。

所以找原根大概是O(n0.25/2)的。

找到之后枚举次方就可以了，因为是充分条件。

想剪个好枝却剪烂的某人在HDU上留下了5个WA... ...

#include #include #include #include #include #include #include #define LL long long int #define ls (x 1 using namespace std; const int N = 1000000+10; int P[N],vis[N],phi[N],tot,n; inline int gcd(int a,int b){return b?gcd(b,a%b):a;} inline void prepare() { phi[1]=1; for(int i=2;i>=1,d=1ll*d*d%Mod)if(z&1)ans=1ll*ans*d%Mod; return ans; } inline bool check(int x) { if(x==2 || x==4)return 1; if((x&1)^1)x>>=1; for(int i=2;P[i]

【本文地址】

公司简介

联系我们