扩展 BSGS
2021/6/1 10:20:59
本文主要是介绍扩展 BSGS,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
首先你要知道什么是 BSGS。
BSGS 用于求解形如 \(a^x\equiv b\pmod p\) 的高次同余方程,其中保证 \(p\) 为质数。
根据费马小定理定理,当 \(p\) 为质数时,\(a^{p-1}\equiv 1\pmod p\)。
所以当 \(x\) 有解 \(>p-1\) 时,也必然有 \(y=x-(p-1)\) 为方程的解,换言之,保证 \(0\sim p-1\) 内有解,或者无解。
设 \(t=\sqrt p\),假设解为 \(t\times i-j\),\(i,j\) 的取值均只有 \(t\) 种,可以事先枚举存入 Hash_Table / Map 里。
因为 \(a^{t\times i-j}\equiv b\pmod p\),所以有 \(a^{t\times i}\equiv b\times a^j\pmod p\),再次枚举 \(j\) 的取值后在之前的表中查找即可。
时间复杂度就为 \(O(\sqrt p)\),当然用 Map 带个 \(\log\)。
int BSGS(int a, int b, int p){ Hash.clear(); int t = (int)sqrt(p) + 1; b %= p; for(int i = 0; i < t; i ++){ int val = 1LL * b * Pow(a, i, p) % p; Hash.insert(val, i); } a = Pow(a, t, p); if(a == 0) return b == 0 ? 1 : -1; for(int i = 0; i <= t; i ++){ int val = Pow(a, i, p); int j = Hash.find(val); if(j >= 0 && i * t - j >= 0) return i * t - j; } return -1; }
扩展 BSGS,即不保证 \(p\) 为素数。
假设 \(d=\gcd(a,p)>1\),若 \(b\ {\rm mod}\ p\not = 0\),就无解。
否则因为 \(a\times d\equiv b\times d\pmod {p\times d}\) 等价于 \(a\equiv b\pmod {p}\),可以直接消去。
直到 \(a,p\) 互质,假设总共用了 \(k\) 个 \(a\),那 \(k\) 个 \(a\) 消去后的乘积为 \(A\),除后的 \(b,p\) 为 \(B,P\),则问题等价于。
\(A\times a^{x-k}\equiv B\pmod P\),再转化一下变为 \(a^{x-k}\equiv B\times Inv(A,P)\pmod P\)。(\(Inv(A,P)\) 表示 \(A\) 在\({\rm mod}\ P\) 意义下的逆元)
这是标准的 BSGS。
模板题放这,卡常卡的人都傻掉了。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N = 1e6 + 10; const int MOD = 999991; int a, p, b; inline int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar(); while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } struct Hash_Table{ int cnt, head[N], nxt[N], val[N], num[N]; void clear(){ cnt = 0; memset(head, 0, sizeof(head)); } void insert(int v, int k){ int u = v % MOD + 1; for(int i = head[u]; i; i = nxt[i]) if(val[i] == v){num[i] = k; return;} nxt[++ cnt] = head[u]; val[cnt] = v, num[cnt] = k; head[u] = cnt; } int find(int v){ int u = v % MOD + 1; for(int i = head[u]; i; i = nxt[i]) if(val[i] == v) return num[i]; return -1; } } Hash; inline int Gcd(int a, int b){ while(b){ int c = a; a = b, b = c % b; } return a; } inline int exGcd(int a, int b, int &x, int &y){ if(!b){x = 1, y = 0; return a;} int d = exGcd(b, a % b, x, y); int z = x; x = y, y = z - a / b * y; return d; } inline int Pow(int a, int b, int p){ int sum = 1; for(; b; b >>= 1){ if(b & 1) sum = 1LL * sum * a % p; a = 1LL * a * a % p; } return sum; } inline int Inv(int a, int p){ int x, y; exGcd(a, p, x, y); return (x % p + p) % p; } inline int BSGS(int a, int b, int p){ Hash.clear(); int t = (int)sqrt(p) + 1; b %= p; for(int i = 0; i < t; i ++){ int val = 1LL * b * Pow(a, i, p) % p; Hash.insert(val, i); } a = Pow(a, t, p); if(a == 0) return b == 0 ? 1 : -1; for(int i = 0; i <= t; i ++){ int val = Pow(a, i, p); int j = Hash.find(val); if(j >= 0 && i * t - j >= 0) return i * t - j; } return -1; } inline int exBSGS(int a, int b, int p){ a %= p, b %= p; if(b == 1 || p == 1) return 0; int k = 0, d, A = 1; while((d = Gcd(a, p)) > 1){ if(b % d != 0) return -1; k ++; b /= d, p /= d, A = 1LL * A * (a / d) % p; if(A == b) return k; } int ans = BSGS(a, 1LL * b * Inv(A, p) % p, p); if(ans == -1) return -1; return ans + k; } int main(){ a = read(), p = read(), b = read(); while(a){ int ans = exBSGS(a, b, p); if(ans == -1) puts("No Solution"); else printf("%d\n", ans); a = read(), p = read(), b = read(); } return 0; }
这篇关于扩展 BSGS的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性