从阶到原根和指标

感觉原根很玄妙啊

阶

定义

满足的最小$x$称为$a$关于$p$的阶，记为$\delta_p(a)$，简写为$\delta (a)$

性质

2. $\delta(a^k)=\dfrac {\delta(a)}{\gcd(\delta(a),k)}$
3. $\gcd(\delta(a),\delta(b))==1\Leftrightarrow \delta(ab)==\delta(a)\delta(b)$

求法

根据性质$1$，$\delta(x)|\phi(x)$，所以只要求出$phi(x)$，依次枚举其因数判断

原根

定义

$\delta_P(g)==\phi(P)$，则$g$是$P$的原根

性质

1. 时，才存在原根

求法

将$\phi(P)$质因数分解存储在$p[]$中 然后从$2$开始枚举判断，如果对于$\forall p_i\in p[]$，有，则$x$是$P$的原根(一开始分子直接写了$P$,但是因为数据弱一直水过了？？)

指标

定义

如果$\gcd(b,P)==1$，那存在$a,0\le a < \phi(P)$，满足，称$a$为$b$关于$P$的指标，记，简记

性质

求法

求出原根$g$，然后BSGS。