扩展BSGS用于解决下列方程，且对于a,c是否互质没有要求 a x ≡ b ( m o d c ) a^x \equiv b \pmod c ax≡b(modc) 以下是洛谷4195（【模板】扩展BSGS）的代码 相应的例题还有HDU2815，都是扩展BSGS的裸题
#include <iostream> #include <cstdio> #include <map> #include <cmath> #include <algorithm> using namespace std; typedef long long ll; ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); } ll quickpow(ll base,ll n,ll mod){ ll ans=1; while(n){ if(n&1) ans = (ans*base)%mod; base = (base*base)%mod; n>>=1; } return ans; } ll solve(ll a,ll b,ll c){ ll n = 0,d=gcd(a,c),t=1; while(d!=1){ if(b%d) return -1; b/=d; c/=d; t=(t*(a/d))%c; n++; if(t==b) return n;//处理小于等于n的情况 d=gcd(a,c); } ll m = ceil(sqrt(c)); map<ll,ll> mp; mp.clear(); ll org=b%c; mp[org]=0; for(int i=1;i<=m;++i){ org=(org*a)%c; mp[org]=i; } ll h = quickpow(a,m,c); ll g = (h*t)%c; for(int i=1;i<=m;++i){ if(mp.count(g)){ ll t = i*m-mp[g]+n; return t; } g=(h*g)%c; } return -1; } int main(){ ll a,b,c; while(~scanf("%lld%lld%lld",&a,&c,&b) && (a||b||c)){ ll ans = solve(a,b,c); if(ans==-1) printf("No Solution\n"); else printf("%lld\n",ans); } }