这样原式变为(A^{im-j}equiv B(mod C))
移项得到(A^{im}equiv BA^j(mod C))
大小步中的"小步"就是从(0)到(m-1)枚举(j)（相当于个位），将((BA^j,j)(mod C))记录进哈希表
然后“大步”就是枚举(i)，相当于枚举(m)进制的第(2)位然后对于每一个(A^{im}(mod C))进入哈希表查找是否存在，若存在一定是最小值直接返回即可。
因为c++整除的性质，一定要确保枚举的i超过C，否则会遗漏答案
注意答案只会在(C)以下，如果超过(C)还没找到就可以返回(-1)了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#define ll long long
#define re register
#define MOD 76543
using namespace std;
int T,aa,bb,cc,K;
int top,hs[MOD],id[MOD],head[MOD],next[MOD];
ll x,y;
map<int,int> a;
void insert(int x, int y)
{
int k = x%MOD;
hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++;
}
int find(int x)
{
int k = x%MOD;
for(int i = head[k]; i != -1; i = next[i])
if(hs[i] == x)
return id[i];
return -1;
}
ll BSGS(ll a,ll b,ll c)
{
a%=c,b%=c;//一定别忘了取模 1
if(a==0&&b==0) return 1;//最小整数解 2
if(gcd(a,c)!=1) return -1;// 3 因为题目保证是质数，不互质的话一定是倍数关系，取模后是0，0的任意次方都只能是0(0^0除外)
if(b == 1)
return 0; // 4
//取模之后的gcd答案一定为C，此时C是质数，即使扩展BSGS也无解
memset(head, -1, sizeof(head));//数组不清空，爆零两行泪
top = 1;
int m = sqrt(c*1.0), j;
long long x = 1, p = 1;
for(int i = 0; i < m; ++i, p = p*a%c)
insert(p*b%c, i);//存的是(a^j*b, j)
for(long long i = m; ;i += m)//此时p为a^m
{
if( (j = find(x = x*p%c)) != -1 )
return i-j; //a^(ms-j)=b(mod c)
if(i > c)
break;
}
return -1;
}
1.当(a)在模(b)意义下有逆元的充要条件是(gcd(a,b)=1)
上面做法虽然用(a^{im-j})而不是(a^{im+j})躲过了逆元操作
但实际上这个操作的逆运算如果不保证(A,C)互质时不成立的，所以(BSGS)的前提是(A,C)互质
2.还有一定要注意C是否为质数，如果为质数且(A,C)不互质，则(A)为倍数，这时候考虑B是否为0，否则(BSGS)和扩展(BSGS)都无解
因为扩展的要让(C)除一个数，无法整除则无解。
3.注意特判的顺序，先取模，再考虑(a==0,b==1)或(a==0,b==0)的情况下，最后再判无解
(Ext. BSGS)
当(A,C)不互质时
1.首先对于一般的离散对数问题(A^xequiv B(mod C)),一定可以写成(A^x=kC+B)
2.令(d=gcd(A,C))，将两边同时除以(d)，得到(frac{A}{d}A^{x-1}=kC_2+B_2)
3.注意(A)是没有变的，所以(A,C)任然可以互质，重复以上操作直到(A,C)互质，令(D=prodlimits_{i=1}^n)，转换为(Dcdot A^{x-n}=kC_n+B_n)即(Dcdot A^{x-n}equiv B_n(mod C_n))，变为互质情况，(BSGS)即可
4.由于这里的指数是(x-n)，需要特判断(x=0,1,cdots n)时等式是否成立。
一般只用特判(50)层就够了，因为是(log(C))的
警告！警告！使用前最好验证一下，因为扩展的BSGS我没写过题！
警告！警告！使用前最好验证一下，因为扩展的BSGS我没写过题！
警告！警告！使用前最好验证一下，因为扩展的BSGS我没写过题！
#define mod 76543
int hs[mod],head[mod],next[mod],id[mod],top;
void insert(int x,int y)
{
int k=x%mod;
hs[top]=x,id[top]=y,next[top]=head[k],head[k]=top++;
}
int find(int x)
{
int k=x%mod;
for(int i=head[k];i!=-1;i=next[i])
if(hs[i]==x)
return id[i];
return -1;
}
int BSGS(int a,int b,int c)
{
memset(head,-1,sizeof(head));//数组不清空，爆零两行泪
top=-1;
if(a==0&&b==0) return 1;
if(b==1)
return 0;
long long d=1;
int cnt=0;
long long r=1;
for(int i=0;i<50;++i)
{
if((r-b)%c==0)
return i;
r*=a;
r%=c;
}//最多50层就够了
while((d=gcd(a,c))!=-1)
{
if(b%d) return -1;//如果不能整除说明无解，因为此时没法用逆元
cnt++;
b/=d,c/=d;//注意让b先取模
}
int m=sqrt(c),j;
for(int j=0;j<m;++j,p=p*a%c)
insert(p*b%c,j);//注意取模，存的是(a^j*b,j);
for(int i=m;;i+=m)//因为是减法，所以从m开始枚举
{
if((j=find(x=x*p%c))!=-1)//p从一开始就是a^m每次乘p相当于a^i
return i-j;//im-j
if(i>c)//里面找不到循环节外不可能找到了
break;
}
return -1;
}