专栏文章

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

CChase12345
P11961题解参与者 14已保存评论 18

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
18 条
当前快照
1 份
快照标识符
@mipth09p
此快照首次捕获于
2025/12/03 17:40
3 个月前
此快照最后确认于
2025/12/03 17:40
3 个月前
查看原文
这道题蓝题好像确实可以，但似乎只是下位蓝。本人并没有去现场考试，但是听 浮光掠影大佬说他们 5 级考场有人哭了。。。
为了尝试做这一道题，先证明 gi mod pg^i \bmod p 具有余数周期性规律：
gp−1≡g2p−2≡1(modp)g^{p-1} \equiv g^{2p-2} \equiv 1 \pmod{p}
则若它具有周期性规律，则周期必定是 p−1p-1 的约数，而且 gi×gp−1≡gi+p−1≡gi×1≡gi(modp)g^i \times g^{p-1} \equiv g^{i+p-1} \equiv g^i \times 1 \equiv g^i \pmod{p} 所以 gi mod pg_i \bmod p 具有余数周期性规律，且以 p−1p-1 为一个周期。当然，不排除以 p−1p-1 的因数为周期的情况。
那么如果 p−1p-1 的约数中，存在 aa，且 ga≡1(modp)g^a \equiv 1 \pmod{p}，则这个周期提前结束， 你也可以理解为 gg 必定不是 pp 的原根。
这个时候有人要问了：有没有可能会在不是 p−1p-1 的约数 bb 提前结束周期？ 那么这样显然是与原来的结论矛盾，因为如果不是在 p−1p-1 的约数 aa 提前结束周期，而且也在 p−1p-1 的约数 bb 前结束周期，这可能吗？一个数列（不是全部数相同的情况下）怎么可能有两个不等价的周期？所以只要验证每个 p−1p-1 的约数 aa 是否满足 ga≡1(modp)g^a \equiv 1 \pmod{p} 即可。时间复杂度 O(Tnlog⁡n)O(T \sqrt{n} \log n)。我这里的变量不是题目的变量，所以可能有点那啥，这种题我居然没有一眼，小六要被小五单调队列了 qwq。
CPP
#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");
	}
}

评论

共 18 条评论，欢迎与作者交流。

正在加载评论...