金融平台网站开发,ps个人网站制作流程,seo教程网站,宿迁558网络专业做网站目录 bsgs问题 或 poj2417#xff1a;概述代码exbsgs鸣谢 \(gzy gzy gzy\)bsgs问题 或 poj2417#xff1a; 给定质数\(p\)#xff0c;给定\(a\),\(b\),\((a,p)1\) 求出最小的整数x#xff0c;使得\(a^{x}≡b(mod p)\) 概述 由费马小定理可以知道\(a^{xp-1}≡a^{x}≡b(mod p… 目录 bsgs问题 或 poj2417概述代码exbsgs鸣谢 \(gzy gzy gzy\) bsgs问题 或 poj2417 给定质数\(p\)给定\(a\),\(b\),\((a,p)1\) 求出最小的整数x使得\(a^{x}≡b(mod p)\) 概述 由费马小定理可以知道\(a^{xp-1}≡a^{x}≡b(mod p)\) 所以如果有解那\([0,p-1]\)区间内一定会出现解 让\(msqrt(p)\)\(x\)可以表示为\(m*i-j\) 那\(m,i,j\)都是在根号规模的\(a^{m*i-j}≡b(mod p)\)\(\frac{a^{m*i}}{a^{j}}≡b(mod p)\)\(a^{m*i}≡b*a^{j}(mod p)\) 右边\(hash\)表一般都用stl的map存在所有的j取值 左边暴力枚举i(因为是-j所以从1枚举要不然就成负数了找出来的就不一定是最小解) 如果\(a^{m*i}\)在hash表中存在那就有解也是最小解结束吧 如果根号范围内还没有解那就真的没解 算法思想分块 算法缺陷p是质数 算法复杂度\(\sqrt{n}\)\(map\)常数也许很高 代码 #include iostream
#include cmath
#include map
#include cstdio
#define ll long long
using namespace std;
ll a,b,p;
mapll,ll hasH;
int main() {while(scanf(%lld%lld%lld,p,a,b)!EOF) {ll mfloor(sqrt(p));hasH.clear();ll tmp1;hasH[b]1;for(ll i1;im;i) tmptmp*a%p,hasH[tmp*b%p]i1;ll xxtmp,i1,ans-1;for(;im;i) {if(hasH[xx]) {ansm*i%p-(hasH[xx]-1);break;}xxxx*tmp%p;}if(ans-1) puts(no solution);else printf(%d\n,ans);}return 0;
} exbsgs 咕咕咕咕 鸣谢 \(gzy gzy gzy\) 转载于:https://www.cnblogs.com/dsrdsr/p/10352136.html
