bzoj3239 Discrete Logging

題目

離散對數裸題，這道題中p是素數，是以用一般BSGS就好了，這個東西十分巧妙呀。

ax≡b(mod p) 我們可以設 x=Ap√+B ，其中， 0≤A≤p√ , 0≤B<p√ 。

那麼，我們可以得到 aAp√≡ba−B(mod p) ,我們枚舉一下，用map判一判就好了。

還有一點就是，可以不用算逆元，我們可以令 x=Ap√−B ，就得到 aAp√≡baB(mod p) ,A、B的範圍改一改就好了。

//BSGS
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll a,b,p,p1,tmp,tmp1,ans;
map <ll,ll> E;
bool flg;
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%lld%lld%lld",&p,&a,&b)!=EOF)
    {
        if(b==){
            printf("0\n");continue;
        }
        E.clear();
        p1=sqrt(p);
        tmp=;
        for(int i=;i<p1;i++)E[(b*tmp)%p]=i,tmp=(tmp*a)%p;
        tmp1=;flg=false;ans=~>>;
        for(int j=;j<=p1+;j++)
        {
            tmp1=(tmp1*tmp)%p;
            if(E.count(tmp1)){
                ans=min(ans,j*p1-E[tmp1]);
                flg=true;
                break;
            }
        }
        if(flg)printf("%d\n",ans);
        else printf("no solution\n");
    }
    return ;
}