BSGS ! x

一.引入:

若存在一个式子a^b ≡ c (mod p) (p ≡ 1000000007,且0<a,b,c<p)

　　已知a,b,求c.

　　　　这不就是快速幂嘛!

　　已知a,c,求b.

　　　　这就是我们需要研究的问题!用到了BSGS!

题目链接:poj 2417 bsgs

二.概念

BSGS:

又名大步小步算法.具体的我也不清楚啦~

那么发明来做什么事情呢?

如上所述:

　　就是用来求解a^x ≡ b (mod p)这样的式子

　　　　PS:已知a,b,p

　　　　　　　　求最小x

三.做法

首先,我们将x用i*m-j来表示,其中我们的m=seil(sqrt(p)),(seil为向上取整)

然后我们用i*m-j代替掉x,所以原式就变成了这个样子

　　　　　　　　a^(i * m-j) ≡ b (mod p)

又因为a^(i * m-j) => a^(i * m)/a^j

所以原式又变了模样:

　　　　　　　　a^(i * m)/a^j ≡ b (mod p)

又因为在"≡"(同余号)的两侧同时乘以一个相同的数依旧是成立的,如果不明白可以手动模拟一下,

给出个栗子~

　　3 ≡ 10 (mod 7),当两边同乘以5时式子变成: 15 ≡ 50 (mod 7)

　　因为15%7==1&&50%7==1,所以原式依旧成立

所以将式子两边同时乘以a^j

那么式子就又发生了改变:

　　　　　　　　a^(i * m) ≡ b * a^j (mod p)

　　　 =　(a^m)^i ≡ b * a^j (mod p)

所以问题就简单多了!

因为a^m是常数,b是常数,p也是常数,所以只有 i 跟 j 是未知的,暴力枚举!

但是有一点是我们不能够忘记的:

m的取值范围:1 —— p(p是当b==0时),所以

首先将 j 从1 到 p-1 进行枚举一遍,求出b * a^j 的值丢到hash(大佬是用map做的)里面咯(讲真hash不会用...怪我咯?)

　　思路是这样的:(其实就是hash啦~)

　　　　　　　　(b*a^j)%p(如果p太小换成另外一个比较大的质数)作为下标,里面存着当前计算出来的数,以及当前的 j (可以用vector~)

然后,枚举 j ,我们大可以设a^m==c

将 i 从 1 到p-1枚举一遍,如果求出的数在hash里面找到了,则说明当前的数就是 i (能够成立的) 最小值,跳出循环,用当前的i,以及记录下来的 j 计算对应的 i 求出 x

则x就是最小的解

C++代码实现:

(map方法:)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<cmath>

using namespace std;

typedef long long LL;

LL a,b,c;

map<LL,LL> mp;

LL qsm(LL m)

{

    LL n = a;

    if(m == ) return ;

    LL t = qsm(m/);

    t = 1LL*t*t%c;

    if(m&) 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==)   //判断a,c 是否互质，因为c 是质数，所以直接判断是否整除即可

        {

            printf("no solution\n");

            continue;

        }

        LL m=ceil(sqrt(c));

        LL ans;

        for (LL j=; j<=m; j++)

        {

            if (j==)

            {

                //当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=;

        bool p=false;

        for (LL i=; 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);

                p=true;

                break;

            }

        }

        if (!p)

            printf("no solution\n");

    }

}

End.

巴特西

BSGS ! x

最新文章

热门文章