P2485 [SDOI2011]计算器
2018-06-17 22:34:49来源:未知 阅读 ()
题目描述
你被要求设计一个计算器完成以下三项任务:
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!”。
输入输出样例
3 1 2 1 3 2 2 3 2 3 3
2 1 2
3 2 2 1 3 2 2 3 2 3 3
2 1 0
4 3 2 1 3 2 2 3 2 3 3 2 4 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实现绘制两个矩形,并标识出重叠的部分
下一篇:逆元模板
- 【洛谷】P1022 计算器的改良-全AC题解 2019-10-29
- VS2017 + QT5 + C++开发环境搭建和计算器Demo测试 2019-01-01
- 手搓一个C语言简单计算器。 2018-12-04
- C语言,简单计算器【上】 2018-06-18
- 03-c#入门(简易存款利息计算器v1.0) 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash