P2485 [SDOI2011]计算器

2018-06-17 22:34:49来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

你被要求设计一个计算器完成以下三项任务:

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c++利用MFC实现绘制两个矩形,并标识出重叠的部分

下一篇:逆元模板