首页 > 代码库 > bsgs BSGS
bsgs BSGS
Question:
had know a,b,c;
ask min x;
made a^x=b(mod c);
think:
make m=ceil(sqrt(c));
make x=i*m-j;
so a^(i*m-j)=b(mod c)
so a^(i*m)/a^j=b(mod c)
so a^(i*m)=b*a^j(mod c)
easy to meijv i,j to full this deng shi
ANS:
answer=min(i*m-j);
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<map> 6 #define ll longlong 7 #define readln(n) scanf("%lld",&n); 8 #define writeln(n) printf("%lld",n); 9 10 using namespace std; 11 12 map<ll,int>mp; 13 14 inline ll f(ll a,ll b,ll mod) 15 { 16 ll ans=1; 17 while(b) 18 { 19 if(b&1) ans=ans*a%mod; 20 a=a*a%mod; 21 b>>=1; 22 } 23 return ans; 24 } 25 26 int main() 27 { 28 ll n;//a^x=b(mod)c,a^(i*m)=b*(a^j)(mod) 29 readln(n); 30 ll a,b,c; 31 readln(a);readln(b);readln(c); 32 if(!a%c){printf("!!!"); return 0; } 33 ll m=ceil(sqrt(c)); 34 ll ans=b%c; 35 mp[ans]=0; 36 for(int i=1;i<=m;i++) 37 { 38 asn=(ans*a)%c; 39 mp[ans]=i; 40 } 41 ll ff=f(a,m,c); 42 ans=1; 43 bool flag=1; 44 for(int i=1;i<=m;i++) 45 { 46 ans=ans*f%c; 47 if(mp[ans]) 48 { 49 ll answer=i*m-mp[ans]; 50 writeln((answer%c+c)%c); 51 flag=0; 52 } 53 } 54 if(!flag) 55 printf("!!!"); 56 }
bsgs BSGS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。