求解 A^x ≡ B mod C C是质数 的最小非负整数解
证明:A^x ≡ A^(x%φ(C)) mod C
A^(x%φ(C)) ≡ A^(x-k*φ(C)) ≡ (A^x)/ A^(k*φ(C)) ≡ A^x mod C
所以枚举的话,x只需要枚举[0,φ(c)-1]
若x在[0,φ(C)-1]范围内有解,则同余方程有解,否则无解
令m=ceil(sqrt(m)),x=i*m-j
A^(i*m-j) ≡ B mod C
A^(i*m) ≡ B* A^j mod C
将 B* A^j modC j∈[1,m] 存入哈希表
从小到大枚举i,找到的第一个 A^(i*m) mod C在哈希表中,i*m-j 就是答案
为什么 m=ceil(sqrt(C))
因为 x<φ(C)=C-1,所以 i*m-j<C-1,i*m<C-1+j
i∈[1,m],所以 m<sqrt(C-1+j)
为什么找到的最小的i,i*m-j 就是答案
因为在将 B* A^j 存入哈希表时,值如果相同的话,会用大的j替换小的j
i*m-j ,i相同时,j越大值越小
从小到大枚举i,A^(i*m) 的增长幅度 要大于A^j,所以i越小越好
void bsgs()
{
mp.clear();
int m=ceil(sqrt(C));
int mul=B;
mp[B]=0;
for(int j=;j<=m;++j)
{
mul=1LL*A*mul%C;
mp[mul]=j;
}
int am=Pow(A,m,C);
mul=;
for(int j=;j<=m;++j)
{
mul=1LL*mul*am%C;
if(mp.find(mul)!=mp.end())
{
printf("%d\n",j*m-mp[mul]);
return;
}
}
puts("No solution");
}