题解：P11961 [GESP202503 五级] 原根判断

· · 题解

这道题蓝题好像确实可以，但似乎只是下位蓝。本人并没有去现场考试，但是听 @浮光掠影 大佬说他们 5 级考场有人哭了。。。

为了尝试做这一道题，先证明 g^i \bmod p 具有余数周期性规律：

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

则若它具有周期性规律，则周期必定是 p-1 的约数，而且 g^i \times g^{p-1} \equiv g^{i+p-1} \equiv g^i \times 1 \equiv g^i \pmod{p} 所以 g_i \bmod p 具有余数周期性规律，且以 p-1 为一个周期。当然，不排除以 p-1 的因数为周期的情况。

那么如果 p-1 的约数中，存在 a，且 g^a \equiv 1 \pmod{p}，则这个周期提前结束， 你也可以理解为 g 必定不是 p 的原根。

这个时候有人要问了：有没有可能会在不是 p-1 的约数 b 提前结束周期？ 那么这样显然是与原来的结论矛盾，因为如果不是在 p-1 的约数 a 提前结束周期，而且也在 p-1 的约数 b 前结束周期，这可能吗？一个数列（不是全部数相同的情况下）怎么可能有两个不等价的周期？所以只要验证每个 p-1 的约数 a 是否满足 g^a \equiv 1 \pmod{p} 即可。时间复杂度 O(T \sqrt{n} \log n)。我这里的变量不是题目的变量，所以可能有点那啥，这种题我居然没有一眼，小六要被小五单调队列了 qwq。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long; 

i64 fpow(i64 a, i64 b, i64 p) {
    i64 ret = 1;
    for (; b; a = a * a % p, b >>= 1)
        ret = ret * ((b & 1) ? a : 1) % p;
    return ret;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        i64 a, p;
        bool res = 1;
        cin >> a >> p;
        res = (fpow(a, p - 1, p) == 1);
        for (int i = 2; i * i <= p - 1; i++)
            if ((p - 1) % i == 0 && (fpow(a, i, p) == 1 || fpow(a, (p - 1) / i, p) == 1))
                res = 0;
        cout << (res ? "Yes\n" : "No\n");
    }
}