BSGS

bsgs算法，又称大小步算法（某大神称拔山盖世算法）。

主要用来解决 A^x=B(mod C)(C是质数)，都是整数，已知A、B、C求x。（poj 2417 Discrete Logging）

具体步骤如下：

先把x=i*m-j，其中m=ceil(sqrt(C))，（ceil是向上取整）。

这样原式就变为A^(i*m-j)=B(mod C)，

再变为A^j×B=A^(m*i) (mod C)。

枚举j(范围0-m),将A^j×B存入hash表

枚举i(范围1-m),从hash表中寻找第一个满足A^j×B=A^(m*i) (mod C)。

此时x=i*m-j即为所求。

在网上看到的其他题解大多用的是x=i*m+j，也可以做，只是会牵扯的求逆元，所以比较麻烦。使x=i*m-j就可以轻松避免这个问题了。

那么肯定有人会有疑问为何只计算到m=ceil(sqrt(C))就可以确定答案呢？

x=i*m-j 也就是x 的最大值不会超过p,那超过p的怎么办？

有一个公式 a^(k mod p-1)=a^k (mod p) 这个公式的推导需要用到费马小定理

k mod p-1可以看做 k-m（p-1） ,原式可化成 a^k/(a^(p-1))^m=a^k (mod p)

根据费马小定理 a^(p-1)=1 (mod p) 其中p为质数，a,p 互质，可得a^k/1^m=a^k (mod p) a^k=a^k (mod p) 得证。

POJ上用G++来测，否则会有编译错误！！！

裸体

POJ Discrete Logging

O(∩_∩)O~ 代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;

typedef long long LL;
LL a,b,c;
map<LL,LL>mp;

LL qsm(LL m) {
    LL n = a;
    if(m==0) return 1;
    LL t=qsm(m/2);
    t=1LL*t*t%c;
    if(m&1) t=1LL*t*n%c;
    return t;
}

int main() {
    //a^im=b*a^j(mod c)
    while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF) {
        mp.clear();
        if(a%c==0) {
            printf("no solution\n");
            continue;
        }
        LL m=ceil(sqrt(c));
        LL ans;
        for(LL j=0; j<=m; j++) {
            if(j==0) {
                //当j=0时，a^j=1, b*a^j=b
                ans=b%c;
                mp[ans]=j;
                continue;
            }
            ans=(ans*a)%c;
            //括号里的ans指a^(j-1)*b,(a^(j-1)*b)*a=(a^j)*b
            mp[ans]=j;
            //在((a^j)*b)%c的位置记录下j
        }
        LL t=qsm(m);//t=a^m
        ans=1;
        bool flag=false;
        for(LL i=1; i<=m; i++) {
            ans=(ans*t)%c;//括号里的ans指的是((a^m)^(i-1))*(a^m)=(a^m)^i=a^(im)
            if(mp[ans]) {
                LL t=i*m-mp[ans];//t=x,因为我们设的x=i*m-j
                printf("%lld\n",t);
                flag=true;
                break;
            }
        }
        if(!flag) printf("no solution\n");
    }
    return 0;
}

自己选的路，跪着也要走完！！！

BSGS

推荐阅读