你被要求设计一个计算器完成以下三项任务:
1、给定y、z、p,计算y^z mod p 的值;
2、给定y、z、p,计算满足xy ≡z(mod p)的最小非负整数x;
3、给定y、z、p,计算满足y^x ≡z(mod p)的最小非负整数x。
为了拿到奖品,全力以赴吧!
输入格式:
输入文件calc.in 包含多组数据。
第一行包含两个正整数T、L,分别表示数据组数和询问类型(对于一个测试点内的所有数
据,询问类型相同)。
以下T 行每行包含三个正整数y、z、p,描述一个询问。
输出格式:
输出文件calc.out 包括T 行.
对于每个询问,输出一行答案。
对于询问类型2 和3,如果不存在满足条件的,则输出“Orz, I cannot find x!”。
输入样例#1:
3 1
2 1 3
2 2 3
2 3 3
输出样例#1:
2
1
2
输入样例#2:
3 2
2 1 3
2 2 3
2 3 3
输出样例#2:
2
1
0
输入样例#3:
4 3
2 1 3
2 2 3
2 3 3
2 4 3
输出样例#3:
0
1
Orz, I cannot find x!
0
思路:
第一问:裸快速幂
第二问:费马小定理 或者 扩展欧几里得(解ax ≡ c (mod b))
第三问:裸BSGS
对于orz的判读
首先我们把上来先把y%p,把等式的左边化成最简形式
对于第二问:先z%p,把等式右边化成最简形式,在这种条件下,如果y==0&&z!=0的情况下 y%b一定等于0而不可能等于z
对于第三问:如果y%p==0无解,因为费马小定理的条件是y与p互素
为了方便理解,我把题目中的变量p改成了mod
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<map>
6 using namespace std;
7 typedef long long LL;
8 LL n,how,y,z,p;
9 map<LL,LL>mp;
10 LL fastpow(LL a,LL p,LL mod)
11 {
12 LL base=a;LL ans=1;
13 while(p!=0)
14 {
15 if(p%2==1)ans=(ans*base)%mod;
16 base=(base*base)%mod;
17 p=p/2;
18 }
19 return ans;
20 }
21 void bsgs(LL y,LL z,LL mod)
22 {
23 mp.clear();
24 if(y%mod==0)
25 {
26 printf("Orz, I cannot find x!\n");
27 return ;
28 }
29 LL m=ceil(sqrt(mod));
30 LL ans;
31 for(LL j=0;j<=m;j++)
32 {
33 if(j==0)
34 {
35 ans=z%mod;
36 mp[ans]=1;
37 continue;
38 }
39 ans=(ans*y)%mod;
40 mp[ans]=j;
41 }
42 ans=1;
43 LL t=fastpow(y,m,mod);
44 for(LL i=1;i<=m;i++)
45 {
46 ans=(ans*t)%mod;
47 if(mp[ans])
48 {
49 LL out=i*m-mp[ans];
50 printf("%d\n",(out%mod+mod)%mod);
51 return ;
52 }
53 }
54 printf("Orz, I cannot find x!\n");
55
56 }
57 int main()
58 {
59 scanf("%d%d",&n,&how);
60 while(n--)
61 {
62 scanf("%d%d%d",&y,&z,&p);
63 y=y%p;
64 if(how==1)
65 printf("%d\n",fastpow(y,z,p));
66 else if(how==2)
67 {
68 z%=p;
69 if(y==0&&z!=0)
70 printf("Orz, I cannot find x!\n");
71 else
72 printf("%d\n",((z%p)*(fastpow(y,p-2,p))%p)%p);
73 }
74 else if(how==3)
75 bsgs(y,z,p);
76 }
77 return 0;
78 }