xdoj1194----(bsgs-用数组实现链表真的是好啊）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 typedef long long LL;
 8 const LL q=2147483647;
 9 const int a=3;
10 const int mod=76543;
11 LL hs[mod],id[mod],head[mod],_next[mod];
12 int top;
13 inline void _inset (LL x, LL y) {
14     hs[top]=y; id[top]=x;//  hs 是健值  id是映射的数 
　　　　　　　　　　　　　　　　　//  所有的值按序号保存 但要根据健值记录它们存放的位置
15     LL k=y%mod;
16     _next[top]=head[k];// 每个链表有一个虚拟头节点  用哈希函数确定应该插入哪个头节点
　　　　　　　　　　         // next 表示下一个元素存放的节点 用来连接链表
17     head[k]=top++;
18 } 
19 LL _find (LL x) {
20     LL k=x%mod;
21     for (LL i=head[k];i!=-1;i=_next[i]) 
22         if (hs[i]==x) return id[i];
23     return -1;
24 }
25 LL bsgs (LL y) {
26     top=1;
27     memset (head,-1,sizeof(head));
28     LL t=sqrt (q)+1;
29     LL tmp=1; 
30     for (int i=0;i<t;i++) {
31         _inset (i,tmp*y%q);
32         tmp=tmp*a%q;
33     }
34     LL ans=1;
35     for (int i=1;i<=t;i++) {
36         ans=ans*tmp%q;
37         LL m=_find(ans);
38         if (m>=0) return i*t-m; 
39     }
40     return -1;
41 }
42 LL q_pow (LL x,LL k) {
43     LL ans=1;
44     while (k) {
45         if (k&1)  ans=ans*x%q;
46         k=k>>1;   x=x*x%q;
47     }
48     return ans;
49 }
50 int main ()
51 {
52     LL  y1,y2;
53     while (~scanf ("%lld %lld",&y1,&y2)) {
54         LL x1=bsgs (y1);
55         LL x2=bsgs (y2);
56         if (x1==-1||x2==-1) printf ("No Solution
");
57         else printf ("%lld
",q_pow (y1,x2) );
58     }
59     return 0;
60 }

抓住青春的尾巴。。。

xdoj1194----(bsgs-用数组实现链表 真的是好啊）

xdoj1194----(bsgs-用数组实现链表真的是好啊）