最近在刷些题，所以如果写题目有些感想会在这边多发点写题心得，顺便赚点批币
题干：印出有几个从 {0,.., p - 1} 打到自己的函数 f （不一定是排列），使得
f(k * x mod p) = k * f(x) mod p
作法：
因为 (Z_p \ {0}, *) 跟 (Z_{p - 1}, +) 同构，可以把 *k 这个操作会生出一些 cycle 分别是
1 -> k -> k^2 -> .. -> 1
印此每个 cycle 大概长这样
a -> a * k -> a * k^2 -> .. -> 1 -> a
特别地，0 自成一个cycle
每个 cycle 可以抓出一个元素来 represent
写作 0, a_1, a_2, a_3, .., a_n
让每个代表打到 {0, .., p - 1} 可以唯一决定一个函数，构造方法就如给定规则
这题其实可以做到跟分解 p - 1 速度一样快，方法是
写作 p - 1 = \prod_i q_i^{r_i}
对于每个 r_i 逐一测试最小的 t_i 使得 0 <= t_i <= r_i 且
a^{q_i^{t_i} \prod_{j != i} q_j^{r_j} = 1
那么 k 的 ord 就是 a^{\prod_i q_i^{t_i}} cycle 数量就是 (p - 1) / ord

最后那个方法是哪个 theorem?

如果要套 thm 我不是很清楚他叫什么但首先可以发现 a 在 Z_p 下的 order 一定是 p - 1 因子设 a 的 order 为 ord 则 a^x = 1 mod p iff x % ord = 0可参考题目 CF1027G该题真的很裸