# 原根¶

## 整数的次数¶

$$m>0$$$$(a, m) = 1$$$$l$$ 是使

$a^l \equiv 1 \pmod m$

$1, a, a^2, \ldots a^{l-1}$

$a^\lambda,\ (\lambda, l)=1,\ 0 < \lambda \le l$

## 原根¶

$g, g^2, \ldots, g^{\varphi(m)}$

$2, 4, p^l, p^{2l}$

$g^{p-1} \not\equiv 1 \pmod{p^2}$

$g^{\varphi(p^{\alpha-1})} \not\equiv 1 \pmod{p^\alpha}$

$S = \{ g^t \mid 1 \le t \le \varphi(m),\ (t, \varphi(m)) = 1\}$

## 次数的计算¶

$f_j = \begin{cases} f_2 & \text{if}\quad 2\le j \le i\\ p^{j-i} f_2 & \mathrm{if} \quad j>i \end{cases}$

## 原根的计算¶

$g^{\frac{\varphi(m)}{q_i}} \neq 1 \pmod{m} \quad(i=1, 2, \ldots, s)$

$a^\lambda, \quad \lambda=1,2,\ldots,d$

$1,2,\ldots p-1$

$$a=2$$，计算 $$2$$$$p$$ 的次数 $$d$$，如果 $$d = p-1$$$$2$$ 就是 $$p$$ 的原根。如果 $$d < p-1$$，在上式中除去下列各数：

$<2>_p, <2^2>_p, \ldots, <2^d>_p$

int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }

int powmod(int a, int b, int p) {
int res = 1;
while (b > 0) {
if (b & 1) res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}

// Finds the primitive root modulo p
int generator(int p) {
vector<int> fact;
int phi = p - 1, n = phi;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
fact.push_back(i);
while (n % i == 0) n /= i;
}
}
if (n > 1) fact.push_back(n);
for (int res = 2; res <= p; ++res) {
bool ok = true;
for (int factor : fact) {
if (powmod(res, phi / factor, p) == 1) {
ok = false;
break;
}
}
if (ok) return res;
}
return -1;
}

// This program finds all numbers x such that x^k=a (mod n)
int main() {
int n, k, a;
scanf("%d %d %d", &n, &k, &a);
if (a == 0) return puts("1\n0"), 0;
int g = generator(n);
// Baby-step giant-step discrete logarithm algorithm
int sq = (int)sqrt(n + .0) + 1;
vector<pair<int, int>> dec(sq);
for (int i = 1; i <= sq; ++i)
dec[i - 1] = {powmod(g, i * sq * k % (n - 1), n), i};
sort(dec.begin(), dec.end());
int any_ans = -1;
for (int i = 0; i < sq; ++i) {
int my = powmod(g, i * k % (n - 1), n) * a % n;
auto it = lower_bound(dec.begin(), dec.end(), make_pair(my, 0));
if (it != dec.end() && it->first == my) {
any_ans = it->second * sq - i;
break;
}
}
if (any_ans == -1) return puts("0"), 0;
int delta = (n - 1) / gcd(k, n - 1);
vector<int> ans;
for (int cur = any_ans % delta; cur < n - 1; cur += delta)
ans.push_back(powmod(g, cur, n));
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
}s

## 原根的一个性质¶

$\mathrm{Q}(p) \equiv \mu(p-1) \pmod{p}$

$S \equiv \dfrac{\varphi(d)}{\varphi(d_1)} \mu(d_1) \pmod(p)$