POJ2417 Discrete Logging | A,C互质的bsgs算法

题目:

给出A,B,C

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

题解:

bsgs算法的模板题

bsgs 全称:Baby-step giant-step

把这种问题的规模降低到了sqrt(n)级别

首先B的种类数不超过C种,结合鸽巢原理,所以A^x具有的周期性显然不超过C

所以一般的枚举算法可以O(C)解决这个问题

但是可以考虑把长度为C的区间分为k块,每块长度为b

显然x满足x=bi-p的形式(1<=i<=k,0<=p<b),所以A^x=B (mod C)移项之后得到A^bi=A^p*B (mod C)

那么这个时候可以预处理出来A^p的所有值(可以用hash表维护)

//注意!hash表在插入之前要先找有没有这个值,如果有的话直接把改了就好

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

一般来说令k=b=sqrt(C)时间复杂度最优

 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
");
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
",i*m-ans);
79         ok=1;
80         break;
81         }
82     }
83     if (!ok)
84         puts("no solution");
85     }
86     return 0;
87 }