2020-2021:teams:legal_string:bsgs

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:bsgs [2020/07/24 10:18]
qgjyf2001 创建
+++ 2020-2021:teams:legal_string:bsgs [2020/07/26 20:21] (当前版本)
qgjyf2001
@@ 行 44: / 行 44: @@
 </code>
+==== 题目 ====
+[[https://www.luogu.com.cn/problem/P3846|洛谷p3846]]
+BSGS模板题
+<code cpp>
+#include <iostream>
+#include <cstdio>
+#include <algorithm>
+#include <cstring>
+#include <cmath>
+#include <map>
+using namespace std;
+typedef long long ll;
+const int mod = 1e6 + 7;
+struct hashtable { // 哈希表
+	int mp[1000700], hsh[1000700];
+	inline int find(int x) {
+		int t = x % mod;
+		while (mp[t] != x && mp[t] != -1) { t = t + 107; if (t >= mod) t -= mod; }
+		return t;
+	}
+	inline void insert(int x, int i) { int f = find(x); mp[f] = x; hsh[f] = i; }
+	inline bool isin(int x) { int f = find(x); return mp[f] == x; }
+	inline int f(int x) { int f = find(x); return hsh[f]; }
+	inline void clear() {
+		memset(hsh, -1, sizeof hsh); memset(mp, -1, sizeof mp);
+	}
+}ht;
+int main() {
+	int b, p, n, m; scanf("%d%d%d", &p, &b, &n);
+	ht.clear(); if (n == 1) return puts("0") & 0;
+	m = ceil(sqrt((double)p)) + 1; int s = 1;
+	for (int i = 1; i <= m; ++i, s = (1LL * s * b) % p, n = (1LL * n * b) % p) ht.insert(n, i); //插入哈希表
+	b = s;
+	for (int i = 1; i <= m; ++i, b = (1LL * b * s) % p)
+	    if (ht.isin(b)) return printf("%d\n", i * m - ht.f(b) + 1) & 0;
+	return puts("no solution") & 0;
+}
+</code>

2020-2021/teams/legal_string/bsgs.1595557106.txt.gz · 最后更改: 2020/07/24 10:18 由 qgjyf2001