Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

Pku 2417 Discrete Logging

题意:
求最小的离散对数B 使得A^B == C (mod P)  P是质数 或者判无解

做法:

数论题..对于比我大的同学肯定觉得很简单。。
由欧拉定理 A^phi(P) == 1 (mod P) (phi(prime)=prime-1)
得到 A^(B+phi(P)) == c (mod P)   A^(B-Phi(P)) ==c (mod P)
所以可以肯定的一点是 如果 [0,phi(P))内无解 由此式子的周期性必然不会有更多解

一个朴素的想法:枚举 B∈[0,phi(P)) 检验 A^B是否 == C(mod P)
问题又出现了 P是个质数 phi(P)=P-1  必然TLE
所以就必须用空间换时间。

设得到的答案是B  B=X*sqrt(P)+Y 注意到X,Y<=sqrt(P)
列式并化简:

A^(X*sqrt(P)+Y) == C (mod P)
(A*sqrt(P))^X*A^Y == C (mod P)

设 T=A*sqrt(P) 原式即 T^X*A^Y == C (mod P)
两边同除以 A^Y  得到 T^X == C/(A^Y) (mod P)

好吧 到现在 做法就已经浮出水面了

我们预处理T^i (mod P) 最多sqrt(P)个 (i<X)
手写hash或者用map直接存下来二元组 (T^X (mod P),X)

然后枚举 Y∈[0,sqrt(P)) 最多sqrt(P)个
对于每个Y 我们求出 C/(A^Y) (mod P)  然后在hash或者map中查找这个值
如果 (C/(A^Y) (mod P),X) 存在  那么说明 X*sqrt(P)+Y 是可以作为答案的

最后答案便是所有满足条件的 X*sqrt(P)+Y 中的最小值。

如果你不知道 C/(A^Y) (mod P) 怎么求
那就继续看下去吧
C/(A^Y) (mod P) == C*((1/A^Y) mod P)
(1/A^Y) (mod P) == (A^Y)^-1 (mod P)
即 (A^Y)^(phi(P)-1) (mod P)
所以 C/(A^Y) (mod P) 就等于C*(A^Y)^(phi(P)-1) (mod P)

这样就解决了此题。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #define Prime 899037
 5 #define oo 2000000005
 6 #define min(a,b) ((a)<(b)?(a):(b))
 7 int P,B,N;
 8 int H[Prime],V[Prime];
 9 inline int pow(int u,int v)
10 {
11     int ret=1;
12     for (int tmp=u;v;v>>=1,tmp=(tmp*(long long)tmp)%P)
13     if (v&1)    ret=(ret*(long long)tmp)%P;
14     return ret;
15 }
16 inline void Hpush(int u,int v)
17 {
18     int t=u%Prime;
19     for (;H[t];)
20     {
21         if (H[t]==u)    return;
22         if (++t==P)    t-=P;
23     }
24     H[t]=u,V[t]=v;
25 }
26 inline int Hpop(int u)
27 {
28     int t=u%Prime;
29     for (;H[t];)
30     {
31         if (H[t]==u)    return V[t];
32         if (++t==P)    t-=P;
33     }
34     return oo;
35 }
36 int main()
37 {
38     for (;scanf("%d%d%d",&P,&B,&N)!=EOF;)
39     {
40         int ret=oo+1;
41         memset(H,0,sizeof(H));
42         memset(V,-1,sizeof(V));
43         int sqrtP=(int)sqrt((double)P),Bsp=pow(B,sqrtP);
44         for (int i=0,val=1;i<=sqrtP;++i,val=(val*(long long)Bsp)%P)
45             Hpush(val,i);
46         for (int i=0,val=1;i<=sqrtP;++i,val=(val*(long long)B)%P)
47         {
48             int h=(N*(long long)pow(val,P-2))%P,v=Hpop(h);
49             if (v<oo&&v*sqrtP+i<ret)    ret=v*sqrtP+i;
50         }
51         if (ret>oo)    puts("no solution");
52         else    printf("%d\n",ret);
53     }
54     return 0;
55 }
56 

posted on 2010-04-21 14:58 jsn1993 阅读(378) 评论(0)  编辑 收藏 引用 所属分类: Math


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理