poj2417 Discrete Logging BSGS裸题

给a^x == b (mod c)求满足的最小正整数x，

用BSGS求，令m=ceil(sqrt(m)),x=im-j，那么a^(i*m)=b*aj%p;,

我们先枚举j求出所有的ba^{j%p,1<=j<m复杂度O（sqrt(c)）,然后枚举1<=i<=m，求出a}(im)在ba^j找满足条件的答案，最后的答案就是第一个满足条件的i*m-j，复杂度O（sqrt（c））

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double eps=1e-6;

const int N=1000000+10,maxn=5000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

map<ll,ll>ma;

inline ll quick(ll a,ll b,ll p)

{

    ll ans=1;

    while(b)

    {

        if(b&1)ans=ans*a%p;

        a=a*a%p;b>>=1;

    }

    return ans;

}

int main()

{

    ll p,a,b;

    while(~scanf("%lld%lld%lld",&p,&a,&b))

    {

        if(a%p==0)

        {

            puts("no solution");

            continue;

        }

        ma.clear();

        ll m=ceil(sqrt(p));

        ll now=b%p;

        ma[now]=0;

        for(int i=1;i<=m;i++)

        {

            now=(now*a)%p;

            ma[now]=i;

        }

        ll ans=-1,t=quick(a,m,p);now=1;

        for(int i=1;i<=m;i++)

        {

            now=now*t%p;

            if(ma[now])

            {

                ans=i*m-ma[now];

                break;

            }

        }

        if(ans!=-1)printf("%lld\n",(ans%p+p)%p);

        else puts("no solution");

    }

    return 0;

}

/********************

********************/

巴特西

poj2417 Discrete Logging BSGS裸题

最新文章

热门文章