一、离散对数
给定 (a,b,m)，存在一个 (x)，使得
(displaystyle a^xequiv bpmod m)
则称 (x) 为 (b) 在模 (m) 意义下以 (a) 为底的 离散对数。
二、BSGS
离散对数：求解关于 (x) 的方程 (a^xequiv bpmod m)。
基本思想：（假设 (gcd(a,m)=1)，那么 (a) 在模 (m) 意义下存在逆元）
考虑类似分块的一个想法。首先设定一个常量 (t)。
设 (x=qt+r)（(0leq r<t)），预处理所有 (a^{qt}) 模 (m) 的值，存到 Hash 表 / map 中。询问时，枚举 (r)，因为 (a^{qt+r}equiv bpmod mLeftrightarrow a^{qt}equiv bcdot a^{-r}pmod m)，所以判断是否存在 (a^{qt}equiv bcdot a^{-r}pmod m) 即可。
预处理的复杂度为 (mathcal{O}(frac{m}{t}))，单次询问的复杂度为 (mathcal{O}(t))。取 (t=sqrt{m})，则复杂度为 (mathcal{O}(sqrt{m}))。
用 map 会多一个 (log)。
不同的写法：如果不想求 (a^{-r})，设 (x=qt-r)（(0leq q,r<t)）， (a^{qt-r}equiv bpmod mLeftrightarrow a^{qt}equiv bcdot a^rpmod m)，预处理 (bcdot a^r) 模 (m) 的值，枚举 (q)，判断是否能找到对应的 (r)。
//Luogu P3846 #include<bits/stdc++.h> #define int long long using namespace std; map<int,int>mp; int a,b,p,ans; int mul(int x,int n,int mod){ int ans=mod!=1; for(x%=mod;n;n>>=1,x=x*x%mod) if(n&1) ans=ans*x%mod; return ans; } int BSGS(int a,int b,int p){ //设 x=qt-r，预处理 b*(a^r)%p，枚举 q，判断是否存在 a^{qt}%p=b*{a^r}%p a%=p,b%=p,mp.clear(); if(!a) return !b?0:-1; int t=ceil(sqrt(p)),x=b; for(int i=0;i<=t;i++) mp[x]=i,x=x*a%p; //枚举 r，预处理 b*(a^r)%p 的值 a=mul(a,t,p),x=a; for(int i=1;i<=t;i++){ //枚举 q if(mp.count(x)) return i*t-mp[x]; //判断是否能找到对应的 r。若找到了，则 x=qt-r 为 x 的一个解 x=x*a%p; } return -1; } signed main(){ scanf("%lld%lld%lld",&p,&a,&b); ans=BSGS(a,b,p); if(~ans) printf("%lld ",ans); else puts("no solution"); return 0; }
二、exBSGS
求解关于 (x) 的方程 (a^xequiv bpmod m)。(m) 可取任意数。
BSGS：(gcd(a,m)=1)，(a) 在模 (m) 意义下存在逆元，可令等式右侧出现 (a) 的幂次。
扩展 BSGS：考虑 (gcd(a,m) eq 1) 的情况。一个想法是，将它转化为 (gcd(a,m)=1)。
设 (d=gcd(a,m))。(a^xequiv bpmod mLeftrightarrow a^x+km=b)，根据裴蜀定理，方程有解当且仅当 (gcd(a,m)mid b)。所以，若 (d mid b)，则原方程无解。
否则，令方程两边同时除以 (d)，得：
(displaystylefrac{a}{d}cdot a^{x-1}+kcdotfrac{m}{d}=frac{b}{d})
此时，若 (gcd(a,m) eq 1)，则令 (x'=x-1,m'=frac{m}{d},b'=frac{b}{d})，重复上述步骤，于是可以一直做下去，直到 (gcd(a,m')=1)。
不妨设重复了 (g) 次，每次求得的 (d=gcd(a,m')) 分别为 (d_1,d_2,cdots,d_g)。记 (prod_{i=1}^g d_i =D)，原式就是：
(displaystylefrac{a^g}{D}cdot a^{x-g}equiv frac{b}{D}pmod {frac{m}{D}})
那么就令 (a'=a,b'=frac{b}{D},m'=frac{m}{D})，跑一遍 BSGS 即可（在枚举 (a^{qt}) 判断时乘上 (frac{a^g}{D})，对应代码中的 ad。最后答案加上 (g) 就行了）。
//Luogu P4195 #include<bits/stdc++.h> #define int long long using namespace std; map<int,int>mp; int a,b,p,ans; int mul(int x,int n,int mod){ int ans=mod!=1; for(x%=mod;n;n>>=1,x=x*x%mod) if(n&1) ans=ans*x%mod; return ans; } int BSGS(int a,int b,int p,int ad){ a%=p,b%=p,mp.clear(); if(!a) return !b?0:-1; int t=ceil(sqrt(p)),x=b; for(int i=0;i<=t;i++) mp[x]=i,x=x*a%p; a=mul(a,t,p),x=a*ad%p; //upd: 原来的 x=a 改为了 x=a*ad%p for(int i=1;i<=t;i++){ if(mp.count(x)) return i*t-mp[x]; x=x*a%p; } return -1; } int exBSGS(int a,int b,int p){ a%=p,b%=p; int g=0,ad=1,d,ans; while((d=__gcd(a,p))!=1){ if(b%d) return -1; g++,b/=d,p/=d,ad=(ad*a/d)%p; if(ad==b) return g; } if(~(ans=BSGS(a,b,p,ad))) return ans+g; return -1; } signed main(){ while(~scanf("%lld%lld%lld",&a,&p,&b)){ if(!a&&!b&&!p) break; ans=exBSGS(a,b,p); if(~ans) printf("%lld ",ans); else puts("No Solution"); } return 0; }
建议把 map 改成 Hash 表 QAQ。