模板—BSGS

你的名字 2021-10-29 07:18 218阅读 0赞

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<map>
    #define LL long long
    using namespace std;
    LL p,b,n;
    
    LL poww(LL a,LL b,LL p)
    {
        LL ans=1;
        while(b)
        {
            if(b&1)ans=ans*a%p;
            a=a*a%p;
            b=b>>1;
        }
        return ans;
    }
    LL bsgs(LL a,LL b,LL p)
    {
        map<LL,LL>mp;mp.clear();
        LL m=ceil(sqrt(p*1.0));
        for(int j=0;j<=m;j++)
        {
            LL val=b*poww(a,j,p)%p;
            mp[val]=j;
        }
        a=poww(a,m,p);
        if(!a)return !b?0:-1;
        for(int i=0;i<=m;i++)
        {
            LL val=poww(a,i,p);
            LL j=mp.find(val)==mp.end()?-1:mp[val];
            if(j>=0 && i*m-j>=0)return i*m-j;
        }
        return -1;
    }
    signed main()
    {
        while(cin>>p>>b>>n)    
        {
            LL ans=bsgs(b,n,p);
            if(ans==-1)puts("no solution");
            else cout<<ans<<endl;
        }
    }

用Hash会更快，map会多个log。

ax≡b (mod p)

令x=i\*m-j,其中m=ceil(sqrt(p));

ai\*m-j≡b (mod p)

ai\*m≡b\*aj (mod p)

枚举j (0<=j<=m)，map\[ b\*aj \]=j,

若a=0，b！=0，则无解，a=0,b=0,则x=0;

枚举i (1<=i<=m)，找到第一个i，使ai\*m≡b\*aj (mod p)成立，i\*m-j即为所求。

转载于:https://www.cnblogs.com/Al-Ca/p/11137470.html

发表评论取消回复

表情：

评论列表（有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

相关数论——求a^x ==b(mod p)中的x————bsgs算法（1.0模板）[个人笔记]

bsgs算法： bsgs算法，又称大小步算法。用来解决**ax == b(mod c)**，求x的问题。 **其中a，b， c是整数， c是质数，且a不是c...

小咪咪/ 2024年04月18日 23:43/ 0 赞/ 46 阅读

相关 Uva1191————思维+bsgs算法

可以看这篇博客][Link 1] include<bits/stdc++.h> define ll long long using namesp...

青旅半醒/ 2024年04月18日 23:25/ 0 赞/ 66 阅读

相关 BSG白山极客挑战赛 B君的圆锥

[B君的圆锥][B] ![male.jpg][] [wwwwodddd][] (命题人) 基准时间限制：1 秒空间限制：131072 KB 分值: 40 B君要用一个

心已赠人/ 2022年08月22日 14:16/ 0 赞/ 150 阅读

相关大步小步算法 (BSGS算法)

大步小步算法是专门用来求解a^x = b(mod n)这种方程的，这种问题也称为离散对数问题。已知a，b，n，且n为素数，求x。模板如下 include <i

水深无声/ 2022年06月12日 03:37/ 0 赞/ 159 阅读

相关 BZOJ2242[SDOI2011]计算器——exgcd+BSGS

题目描述你被要求设计一个计算器完成以下三项任务： 1、给定y,z,p,计算Y^Z Mod P 的值； 2、给定y,z,p，计算满足xy≡ Z ( mod P )的最

约定不等于承诺〃/ 2022年01月05日 15:15/ 0 赞/ 243 阅读

相关 BSGS与exBSGS学习笔记

\\(BSGS\\)用于解决这样一类问题： > 求解\\(A^x ≡B(modP)\\)的最小\\(x\\)，其中\\(P\\)为质数。这里我们采用分块的方法，把\\(x

短命女/ 2022年01月05日 15:05/ 0 赞/ 207 阅读

相关 BSGS

BSGS 用途：给定形如$A^x \\equiv z (mod p)$(p为质数)的式子，给定A、z、p,求满足条件的x的最小值。解法：考虑暴力

男娘i/ 2021年12月15日 06:39/ 0 赞/ 210 阅读

相关 uva 11916 Emoogle Grid （BSGS）

[UVA 11916][] 　　BSGS的一道简单题，不过中间卡了一下没有及时取模，其他这里的100000007是素数，所以不用加上拓展就能做了。代码如下： ![Con

ゞ浴缸里的玫瑰/ 2021年12月14日 12:43/ 0 赞/ 205 阅读

相关 bzoj5104 Fib数列（BSGS+二次剩余）

快AFO了才第一次写二次剩余的题…… 显然应该将Fn写成通项公式（具体是什么写起来不方便而且大家也都知道），设t=((1+√5)/2)n,T=√5N，然后可以得到t-(-1)

向右看齐/ 2021年11月01日 08:44/ 0 赞/ 233 阅读

相关模板—BSGS

include<iostream> include<cstdio> include<cmath> include<map> define

你的名字/ 2021年10月29日 07:18/ 0 赞/ 219 阅读