# E: ヘクト問題解説
原案: hec, 解説: qLethon[(@pu__Ne)](https://twitter.com/pu__Ne)

$\mod p$ での原子根のうち1つを $g$ とする．$g$ は原始根の定義から周期 $p - 1$ である．
$m \mid p - 1$ ($m$は$p - 1$の約数)，$\phi := g^{\frac{p - 1}{m}}$とすると，$\phi^k \pmod{p}$ は周期 $m$ となる．
このとき，$m \gt 2n$ が素数ならば，$A_i = (\phi^{i \times 0}\ \%\ p, \phi^{i \times 1}\ \%\ p, ..., \phi^{i \times (m - 1)}\ \%\ p)$ とすると，$A_1, A_2, A_3, ..., A_n$ は条件を満たす．

周期 $m$ の例: 数列$(1, 2, 3, 1, 2, 3,...)$は周期$3$, $\mod{5}$で，$(2^0, 2^1, 2^2, 2^3,...)$は周期$4$

## 証明
#### 1. $N$ 個の数列は全て異なる
$A_i = A_j \Leftrightarrow \phi^{ik} \equiv \phi^{jk} \pmod{p}\ (k = 0, 1, ..., m - 1)$
$\Leftrightarrow ik \equiv jk \pmod{m}\ (k = 0, 1, ..., m - 1)$
$\Leftrightarrow k = 0\ \lor (k \not= 0 \land i \equiv j \pmod{m})$
よって，$i \not= j \Rightarrow A_{i, k} \not= A_{j, k} (k \not= 0)$
したがって，$A_i \not= A_j (i \not= j)$

#### 2. 各数列の$M$個の要素はすべて整数で、それぞれ$1$以上$P$未満である
$g \not= 0$なので$g^k \not= 0$

#### 3. 各数列の$M$個の数は全て異なる
1.と同様．

#### 4. $1 \le i,\ j \le N$に対して、$\sum_{k = 1}^{M}A_{i, k}A_{j, k} \equiv 0 \pmod{P}$が成り立つ
fact. 1 $\phi^{ij}\phi^{ik} = \phi^{((i + j) \% m)k}$

fact. 2 $\sum_{k = 0}^{m - 1} \phi^{ik} = \sum_{k = 0}^{m - 1} (\phi^i)^k = \frac{1 - \phi^{im}}{1 - \phi^{i}} \equiv 0 \pmod{p}\ (i \not \equiv 0 \pmod{m})$
($\phi$は周期mで，$\phi^0 = 1$だから，$\phi^{im} \equiv 1 \pmod{p}$)

fact. 1, 2から，
$l := (i + j)\ \%\ m$とすると，
$\sum_{k = 0}^{m - 1} \phi^{ij}\phi^{ik} = \sum_{k = 0}^{m - 1} \phi^{lk} \equiv 0 \pmod{p}\ (i + j \not \equiv 0 \pmod{m})$

よって，素数$m \gt 2n$を約数に持つような$p - 1$を探せばいい．ある．
例. (p, m) = (95713, 997)