首页 > > 程序设计 > C/C++ >

05:登月计划

2018-06-17 22:12:40来源：未知阅读 ()

总时间限制:: 40000ms
单个测试点时间限制:: 4000ms
内存限制:: 256000kB

描述

HJA在和学弟学数学，于是便有了一道非常简单的数学题：求满足 a^x^≡= b (mod p) 的最小自然数x。

对于30%的数据，1≤p≤1000。

对于100%的数据，1≤a,b<p≤1e12。

输入

输入数据一行三个正整数a、b、p，我们保证p是一个质数。

输出

一行一个整数代表最小的自然数x，如果不存在这样的x输出-1。

样例输入

2 1 3

样例输出

来源

zhonghaoxi

查看
提交
统计
提问

做了这道题，才发现pb_ds的伟大。。。。

不用pb_ds 80 20000+ms

用了AC 10000+ms。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<map>
 6 #define LL long long 
 7 using namespace std;
 8 LL a,b,c;
 9 map<LL,LL>mp;
10 LL fastmul(LL x,LL p)
11 {
12     LL now=x;
13     LL ans=0;
14     while(p)
15     {
16         if(p&1)
17         {
18             --p;
19             ans=(ans+now)%c;
20         }
21         p>>=1;
22         now=(now+now)%c;
23     }
24     return (ans)%c;
25 }
26 LL fastpow(LL a,LL p,LL c)
27 {
28     LL base=a;LL ans=1;
29     while(p!=0)
30     {
31         if(p%2==1)ans=(fastmul(ans,base))%c;
32         base=(fastmul(base,base))%c;
33         p=p>>1;
34     }
35     return ans;
36 }
37 int main()
38 {
39     // a^x = b (mod c)
40         /*LL x,y,mod;
41         cin>>x>>y>>mod;
42         c=mod;
43         a=x;
44         b=y;*/
45         cin>>a>>b>>c;
46         LL m=ceil(sqrt(c));// 注意要向上取整 
47         mp.clear();
48         if(a%c==0)
49         {
50                printf("-1\n");
51             return 0;
52         }
53         // 费马小定理的有解条件 
54         LL ans;//储存每一次枚举的结果 b* a^j
55         for(LL j=0;j<=m;j++)  // a^(i*m) = b * a^j
56         {
57             if(j==0)
58             {
59                 ans=b%c;
60                 mp[ans]=j;// 处理 a^0 = 1 
61                 continue;
62             }
63             ans=(fastmul(ans,a))%c;// a^j 
64             mp[ans]=j;// 储存每一次枚举的结果 
65         }
66         LL t=fastpow(a,m,c);
67         ans=1;//a ^(i*m)
68         LL flag=0;
69         for(LL i=1;i<=m;i++)
70         {
71             ans=(fastmul(ans,t))%c;
72             if(mp[ans])
73             {
74                 LL out=fastmul(i,m)-mp[ans];// x= i*m-j
75                 printf("%lld\n",(out%c+c)%c);
76                 flag=1;
77                 break;
78             }
79             
80         }
81         if(!flag)
82             printf("-1\n");    
83     return 0;
84 }

不用80

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<map>
 6 #include<ext/pb_ds/assoc_container.hpp>
 7 #include<ext/pb_ds/hash_policy.hpp>
 8 #define LL long long 
 9 using namespace std;
10 using namespace __gnu_pbds;
11 LL a,b,c;
12 gp_hash_table<LL,LL>mp;
13 LL fastmul(LL x,LL p)
14 {
15     LL now=x;
16     LL ans=0;
17     while(p)
18     {
19         if(p&1)
20         {
21             --p;
22             ans=(ans+now)%c;
23         }
24         p>>=1;
25         now=(now+now)%c;
26     }
27     return (ans)%c;
28 }
29 LL fastpow(LL a,LL p,LL c)
30 {
31     LL base=a;LL ans=1;
32     while(p!=0)
33     {
34         if(p%2==1)ans=(fastmul(ans,base))%c;
35         base=(fastmul(base,base))%c;
36         p=p>>1;
37     }
38     return ans;
39 }
40 int main()
41 {
42     // a^x = b (mod c)
43         /*LL x,y,mod;
44         cin>>x>>y>>mod;
45         c=mod;
46         a=x;
47         b=y;*/
48         cin>>a>>b>>c;
49         LL m=ceil(sqrt(c));// 注意要向上取整 
50         mp.clear();
51         if(a%c==0)
52         {
53                printf("-1\n");
54             return 0;
55         }
56         // 费马小定理的有解条件 
57         LL ans;//储存每一次枚举的结果 b* a^j
58         for(LL j=0;j<=m;j++)  // a^(i*m) = b * a^j
59         {
60             if(j==0)
61             {
62                 ans=b%c;
63                 mp[ans]=j;// 处理 a^0 = 1 
64                 continue;
65             }
66             ans=(fastmul(ans,a))%c;// a^j 
67             mp[ans]=j;// 储存每一次枚举的结果 
68         }
69         LL t=fastpow(a,m,c);
70         ans=1;//a ^(i*m)
71         LL flag=0;
72         for(LL i=1;i<=m;i++)
73         {
74             ans=(fastmul(ans,t))%c;
75             if(mp[ans])
76             {
77                 LL out=fastmul(i,m)-mp[ans];// x= i*m-j
78                 printf("%lld\n",(out%c+c)%c);
79                 flag=1;
80                 break;
81             }
82             
83         }
84         if(!flag)
85             printf("-1\n");    
86     return 0;
87 }