BSGS 算法

求解 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");

}