首页 > 代码库 > 离散对数的求解(bsgs)
离散对数的求解(bsgs)
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cmath> 6 #include<map> 7 using namespace std; 8 typedef long long ll; 9 ll q=2147483647,a=3,yy,y2,m,ans,t; 10 map<ll,int>mp; 11 ll mod_pow(ll x,ll n,ll mod){ 12 ll res=1; 13 while(n>0){ 14 if(n&1) res=res*x%mod; 15 x=x*x%mod; 16 n>>=1; 17 } 18 return res; 19 } 20 21 int main(){ 22 while(~scanf("%lld%lld",&yy,&y2)){ 23 mp.clear(); 24 m=ceil(sqrt(q)); 25 for(ll i=0;i<=m;i++){ 26 if(i==0){ 27 ans=yy%q; 28 mp[ans]=i; 29 continue; 30 } 31 ans=ans*a%q; 32 mp[ans]=i; 33 } 34 bool flag=false; 35 ans=1; 36 t=mod_pow(a,m,q); 37 38 39 for(int i=1;i<=m;i++){ 40 ans=ans*t%q; 41 if(mp[ans]){ 42 ll temp=i*m-mp[ans]; 43 ll rr=mod_pow(y2,temp,q); 44 printf("%lld\n",rr); 45 flag=true; 46 break; 47 } 48 } 49 if(!flag){ 50 printf("No Solution\n"); 51 } 52 } 53 return 0; 54 }
离散对数的求解(bsgs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。