原根

如果m > 1， 并且 n 和 m 互质

　　则 $n^tequiv 1(mod m)$

的最小的t，称为n模m的阶（或周期）

则对于任意的$n^xequiv 1(mod m)$

t|x

我们已知$n^{phi (m)}equiv 1(mod m)$

所以

t|$phi(m)$

 

特殊情况时t == $phi(m)$

此时n称为m的原根

求t的方法 先求出$phi(m)$

然后质因子分解  （不能用质因子分解 是所有的因子）

这样：

        int res = phi[n];
        for(int i = 2; i <= sqrt(phi[n] + 0.5); i++)
        {
            if(res % i == 0)
            {
                if(i * i == res)
                    v.push_back(i);
                else
                    v.push_back(i), v.push_back(res / i);
            }
        }

 最小的p使得$n^{p}equiv 1(mod m)$ 的即为t

题目：HDU - 1395

求原根的方法

先把$phi(m)$分解质因子

$phi(m) = p_{1}^{a1}*p_{2}^{a2}*cdots *p_{k}^{ak} $

然后枚举g

如果 对任意的$iin [1, k]$

$g^frac{phi (m)}{p_{i}} eq 1(mod  m)$

则g为m的一个原根