題目:

給出A,B,C

求最小的x使得A^x=B? (mod C)

---

題解:

bsgs算法的模板題

bsgs 全稱:Baby-step giant-step

把這種問(wèn)題的規(guī)模降低到了sqrt(n)級(jí)別

首先B的種類數(shù)不超過(guò)C種,結(jié)合鴿巢原理,所以A^x具有的周期性顯然不超過(guò)C

所以一般的枚舉算法可以O(shè)(C)解決這個(gè)問(wèn)題

但是可以考慮把長(zhǎng)度為C的區(qū)間分為k塊,每塊長(zhǎng)度為b

顯然x滿足x=bi-p的形式(1<=i<=k,0<=p<b),所以A^x=B? (mod C)移項(xiàng)之后得到A^bi=A^p*B (mod C)

那么這個(gè)時(shí)候可以預(yù)處理出來(lái)A^p的所有值(可以用hash表維護(hù))

//注意!hash表在插入之前要先找有沒(méi)有這個(gè)值,如果有的話直接把改了就好

處理出A^b的值,枚舉i,就可以得到答案

一般來(lái)說(shuō)令k=b=sqrt(C)時(shí)間復(fù)雜度最優(yōu)

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<map> 5 #include<cmath> 6 #define MOD 1000007 7 #define EDGE 500000 8 typedef long long ll; 9 using namespace std; 10 ll c,a,b,ok,m,tmp,t,ans,head[MOD],ecnt; 11 struct adj 12 { 13 ll nxt,w,sum; 14 }e[EDGE]; 15 void add(ll x,ll sum) 16 { 17 ll org=x; 18 e[++ecnt].w=x; 19 x%=MOD; 20 for (int i=head[x];i;i=e[i].nxt) 21 if (e[i].w==org) 22 { 23 e[i].sum=sum; 24 return ; 25 } 26 e[ecnt].sum=sum; 27 e[ecnt].nxt=head[x]; 28 head[x]=ecnt; 29 } 30 ll qow(ll x,ll y,ll P) 31 { 32 if (y==0) return 1; 33 if (y&1) return x*qow(x*x%P,y>>1,P)%P; 34 return qow(x*x%P,y>>1,P)%P; 35 } 36 ll find(ll x) 37 { 38 ll org=x; 39 x%=MOD; 40 for (int i=head[x];i;i=e[i].nxt) 41 { 42 if (e[i].w==org) 43 return e[i].sum; 44 } 45 return -1; 46 } 47 int main() 48 { 49 while (scanf("%lld%lld%lld",&c,&a,&b)!=EOF) 50 { 51 memset(head,0,sizeof(head)); 52 ecnt=0; 53 ok=0; 54 if (a%c==0) 55 { 56 puts("no solution"); 57 continue; 58 } 59 m=ceil(sqrt(c*1.0)); 60 tmp=b%c,add(tmp,0); 61 if (b==1) 62 { 63 printf("0\n"); 64 continue; 65 } 66 for (int i=1;i<m;i++) 67 { 68 tmp=tmp*a%c; 69 add(tmp,i); 70 } 71 ll base=qow(a,m,c),tmp=1; 72 for (int i=1;i<=m;i++) 73 { 74 tmp=tmp*base%c; 75 ans=find(tmp); 76 if (ans!=-1) 77 { 78 printf("%lld\n",i*m-ans); 79 ok=1; 80 break; 81 } 82 } 83 if (!ok) 84 puts("no solution"); 85 } 86 return 0; 87 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/mrsheep/p/7920967.html

總結(jié)

以上是生活随笔為你收集整理的POJ2417 Discrete Logging | A,C互质的bsgs算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。