专栏文章

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

RRedshift_Shine
P11961题解参与者 5已保存评论 4

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@mipts74v
此快照首次捕获于
2025/12/03 17:49
3 个月前
此快照最后确认于
2025/12/03 17:49
3 个月前
查看原文
明天就要月考了，但是看到这道题还是想写一下。
然后，思考时间 3min，切。
理论上，以下解法并不要求对“原根”这一概念有额外的事先理解。
首先，根据费马小定理，对于任意质数 pp 和任意小于 pp 的正整数 aa，满足 ap−1≡1(modp)a^{p-1}\equiv 1\pmod p，故可以直接省略第二个条件。
随后，可以证明，对于任何小于 pp 的正整数 xx，对于最小的正整数 kk 满足 xk≡1(modp)x^k\equiv 1\pmod p，k∣(p−1)k|(p-1)。证明也足够显然，若最小的 kk 不是 (p−1)(p-1) 的因数，那么 xp−1≢1(modp)x^{p-1}\not\equiv 1\pmod p，与费马小定理相悖，显然不存在这种情况。
由此，解法显然。枚举 (p−1)(p-1) 的所有因数 ff，若存在 f≠1f\neq 1 且 f≠p−1f\neq p-1 满足 af≡1(modp)a^f\equiv 1\pmod p，则不是原根，否则是。
时间复杂度 O(∑p−1log⁡p)O(\sum \sqrt{p-1}\log p)。
C
// #define Redshift_Debug
#ifdef Redshift_Debug
#define debug(...) fprintf(stderr, __VA_ARGS__)
#include <chrono>
#else
#define debug(...)
#endif
#include <cstdio>

using namespace std;
const int N = 1e5 + 10;
int a, p;
inline int fsp(int x, int y)
{
	int res = 1;
	while (y)
	{
		if (y & 1)
			res = 1ll * res * x % p;
		x = 1ll * x * x % p;
		y >>= 1;
	}
	return res;
}
void init_global()
{
}
void init_local()
{
	scanf("%d%d", &a, &p);
}
void run()
{
	for (int i = 2; i * i <= p - 1; i++)
	{
		if ((p - 1) % i)
			continue;
		if (fsp(a, i) == 1 or fsp(a, (p - 1) / i) == 1)
		{
			puts("No");
			return;
		}
	}
	puts("Yes");
}
int main()
{
#ifdef Redshift_Debug
	auto st = chrono::high_resolution_clock::now();
#endif
	int T = 1;
	scanf("%d", &T);
	init_global();
	while (T--)
	{
		init_local();
		run();
	}
#ifdef Redshift_Debug
	auto ed = chrono::high_resolution_clock::now();
	fprintf(stderr, "%.9lf\n", (ed - st).count() / 1e9);
#endif
}

评论

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

正在加载评论...