po2417 Discrete Logging

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

给出b n p 求l使得，b^l==n (mod p)

学习了一下 BSGS算法。

#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
ll p,b,n;void exgcd(ll c,ll d,ll &x,ll &y){if(!d){x=1;y=0;return ;}exgcd(d,c%d,x,y);ll xx=y,yy=x-(c/d)*y;x=xx;y=yy;
}void work(){ll m=(ll)sqrt(p),bb=1,nn=n,inv,t;map<int,int> num;map<int,bool> app;app[1]=1;num[1]=0;for(int i=1;i<=m-1;i++){bb=bb*b%p;if(!app[bb]){app[bb]=1;num[bb]=i;}}bb=bb*b%p;exgcd(bb,p,inv,t);if(inv>0) inv%=p;else inv=inv%p+p;for(int i=0;i<=m;i++){if(app[nn]){printf("%lld\n",i*m+num[nn]);return ;}nn=nn*inv%p;}printf("no solution\n");
}int main(){while(scanf("%lld%lld%lld",&p,&b,&n)!=EOF) work();return 0;
}

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

---