这道题开头写着：
截止 2025 年 3 月，本题可能超出了 GESP 考纲范围。在该时间点下，原根是 NOI 大纲 8 级知识点（NOI 级），而相对简单的无需原根知识的做法中，使用的费马小定理与欧拉定理也属于 NOI 大纲 7 级知识点（提高级），且均未写明于 GESP 大纲中。需要注意，GESP 大纲和 NOI 大纲是不同的大纲。
而且标的难度是：\color{3498db}提高+/省选−一看就很吓人，导致很多人被这道题吓退。
实际上，这道题的难度有：\color{52c41a}普及+/提高
你需要掌握的知识有：
- 快速幂（橙题难度）
- 费马小定理（黄题难度，因为逆元模板题是黄）
- 反证法（初中数学）
这些知识点最高的是黄，综合应用起来差不多是绿了。
首先要证明一点，使 k 为满足 b^k \equiv 1 \pmod p（p 是质数，b 与 p 互质）的最小正整数的充要条件是：k \mid p-1
使用反证法，假设 k \nmid p-1，根据费马小定理，则必定存在一个 q，使得 0<p-1-qk<k 且 b^{p-1-qk}\equiv 1 \pmod p，因此k 不是满足 b^k \equiv 1 \pmod p 的最小正整数，矛盾，所以 k \mid p-1。
这样就好做了，枚举每个 p-1 的约数即可。时间复杂度 O(T \sqrt{p} \log p)。