avatar
文章
462
标签
13
分类
74

Believe it

bsgs算法

发表于2019-06-12|更新于2019-06-12|ACM学习笔记数学
|阅读量:
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
1
2
3
4
5
6
7
8
9
10
11
// a^x === b   x=lg(a,b)
int bsgs_lg(int a,int b,int mod){
map<int,int>mp;
int sqr=sqrt(mod-1)+1;
for(int i=0;i<sqr;i++) mp[qpow(a,i,mod)]=i; // baby step
for(int i=0;i<mod-1;i+=sqr){ // giant step
int tp=1ll*b*qpow(a,mod-1-i,mod)%mod; // a^(-i)
if(mp.find(tp)!=mp.end()) return i+mp[tp];
}
return -1;// error
}
文章作者: fightinggg
文章链接: http://fightinggg.github.io/butterfly/PSZ23L.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Believe it!
上一篇
多项式
下一篇
杜教筛
avatar
fightinggg
O ever youthful, O ever weeping
文章
462
标签
13
分类
74
Follow Me
公告
This is my Blog
最新文章
2023你好2023-02-06
VPN与代理那些事2022-07-24
CPU架构介绍2022-07-19
docker内部安装软件2022-07-16
白帽子讲Web安全2022-05-25
©2020 - 2023 By fightinggg
框架 Hexo|主题 Butterfly