总时间限制: 40000ms单个测试点时间限制: 4000ms内存限制: 256000kB描述
HJA在和学弟学数学,于是便有了一道非常简单的数学题:求满足 ax ≡= b (mod p) 的最小自然数x。
对于30%的数据,1≤p≤1000。
对于100%的数据,1≤a,b<p≤1e12。
输入输入数据一行三个正整数a、b、p,我们保证p是一个质数。输出一行一个整数代表最小的自然数x,如果不存在这样的x输出-1。样例输入
2 1 3
样例输出
0
来源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 }
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 }