Loading...

(EX)bsgs 学习笔记

check评论:0 条 remove_red_eye浏览量:369 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-02-22

  • $bsgs$

给定$a,b,p$,其中$gcd(a,p)=1$,求最小的$x$使得$a^x\equiv b\pmod p$

令$m=\sqrt p$,设$x=im-j$,则$a^{im}\equiv ba^j\pmod p$

先将$j$从$0$循环到$m$,在$hash$表中存入$ba^j$

然后$i$从$1$到$m$,如果$a^{im}$已存在于表中,就是一组新解,如果$i$最小,$x$就最小

例题:TJOI2007可爱的质数

code:

#include <bits/stdc++.h>
using namespace std;
map<long long,long long> mp;
map<long long,long long> j;
long long a,b,p;
long long ksm(long long qaq,int f)
{
    long long res=1;
    while(f)
    {
        if(f&1)
        {
            res=res*qaq%p;
        }
        qaq=qaq*qaq%p;
        f>>=1;
    }
    return res;
}
int main()
{
    cin>>p>>a>>b;
    long long m=sqrt(p);
    for(int i=0;i<=m;i++)
    {
        mp[b]=1;
        j[b]=i;
        b=b*a%p;
    }
    long long k=ksm(a,m),k1=k;
    for(int i=1;i<=m;i++)
    {
        k1%=p;
        if(mp[k1])
        {
            printf("%lld",i*m-j[k1]);
            return 0;
        }
        k1*=k;
    }
        cout<<"no solution";
}
  • $Exbsgs$

咕咕咕

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名