Poj 2417 Discrete Logging —— BSGS模板

本文主要是介绍Poj 2417 Discrete Logging —— BSGS模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

告诉你B，N，P，让你求最小的L使得

题解：

BSGS模板，大致意思是将L变成ax+b的形式，定下x之后，式子就变成了这样：
$B^b==N{B}^{-ax}(modP)$
那么我们只需要先枚举b(0<=b<=x)，将所有值都记下来，再枚举a，同时查询即可。
这道题如果将x设为$\sqrt{P}$的话会T，或许是我写的教丑，在经过一系列的尝试之后，确定x在2e3~3e3这个范围最优。

#include<stdio.h>
#include<iostream>
#include<map>
#include<math.h>
using namespace std;
#define ll long long
ll mod;
const ll inf=1e10; 
ll qpow(ll a,ll b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
map<ll,int>mp;
int main()
{ll b,n;while(scanf("%lld%lld%lld",&mod,&b,&n)!=EOF){mp.clear();int x=min(2500,(int)sqrt(mod)+1);ll v=1;ll ans=inf;for(int i=0;i<=x;i++,v=v*b%mod){if(mp.count(v))break;mp[v]=i;if(v==n)ans=min(ans,1ll*i);}v=n;ll ret=qpow(b,x);ret=qpow(ret,mod-2);ll top=mod/x+1;for(int i=0;i<=top;i++){if(mp.count(v))ans=min(ans,1ll*i*x+mp[v]);if(v==1&&i!=0)ans=min(ans,1ll*i*x);if(i*x>=ans)break;v=v*ret%mod;}if(ans==inf)printf("no solution\n");else printf("%lld\n",ans);}return 0;
}

这篇关于Poj 2417 Discrete Logging —— BSGS模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---