首页 > 代码库 > Bzoj2242 [SDOI2011]计算器
Bzoj2242 [SDOI2011]计算器
Submit: 3611 Solved: 1400
Description
你被要求设计一个计算器完成以下三项任务：
1、给定y,z,p,计算Y^Z Mod P 的值；
2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；
3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。
Input
输入包含多组数据。
第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。
以下行每行包含三个正整数y,z,p，描述一个询问。
Output
对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。
Sample Input
【样例输入1】
3 1
2 1 3
2 2 3
2 3 3
【样例输入2】
3 2
2 1 3
2 2 3
2 3 3
【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。
3 1
2 1 3
2 2 3
2 3 3
【样例输入2】
3 2
2 1 3
2 2 3
2 3 3
【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。
Sample Output
【样例输出1】
2
1
2
【样例输出2】
2
1
0
2
1
2
【样例输出2】
2
1
0
HINT
Source
第一轮day1
数学
喜闻乐见3 in 1
第一问，快速幂
第二问，扩展欧几里得
第三问，BSGS
提交上去秒WA，于是开始查BSGS的错（一般都会这么想吧），然而并没有发现错。
和黄学长的程序对拍BSGS，有那么几个数据不一样，调试无果，又找了一堆程序对拍，最后确定是黄学长写挂了233
最后发现是task2第48行，(LL)x*b写成了(LL)(x*b),大概是炸了
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<map> 9 #define LL long long 10 using namespace std; 11 const int mxn=100010; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 16 return x*f; 17 } 18 int ksm(int a,int k,int p){ 19 int res=1; 20 while(k){ 21 if(k&1)res=((LL)res*a%p); 22 a=((LL)a*a%p); 23 k>>=1; 24 } 25 return res; 26 } 27 void task1(int a,int k,int p){ 28 printf("%d\n",ksm(a,k,p)); 29 } 30 int gcd(int a,int b){ 31 return (!b)?a:gcd(b,a%b); 32 } 33 void exgcd(int a,int b,int &x,int &y){ 34 if(!b){x=1;y=0;return;} 35 exgcd(b,a%b,x,y); 36 int tmp=x;x=y;y=tmp-a/b*y; 37 return; 38 } 39 void task2(int a,int b,int p){ 40 int x,y; 41 int tmp=gcd(a,p); 42 if(b%tmp){ 43 printf("Orz, I cannot find x!\n"); 44 return; 45 } 46 b/=tmp;a/=tmp;p/=tmp; 47 exgcd(a,p,x,y); 48 x=(LL)x*b%p; 49 while(x<0)x+=p; 50 printf("%d\n",x); 51 return; 52 } 53 map<int,int>mp; 54 void task3(int a,int b,int p){ 55 if(a%p==0){ 56 if(b==0)printf("1\n"); 57 else printf("Orz, I cannot find x!\n"); 58 return; 59 } 60 mp.clear(); 61 int m=sqrt((double)p); 62 int tmp=1; 63 for(int i=0;i<m;i++){ 64 int now=((LL)tmp*b)%p; 65 if(!mp[now])mp[now]=i; 66 tmp=((LL)tmp*a)%p; 67 } 68 int res=1,ans,i; 69 for(i=m;i<=p;i+=m){ 70 res=(LL)res*tmp%p; 71 if(mp[res]){ 72 ans=i-mp[res]; 73 break; 74 } 75 } 76 if(i>p){ 77 printf("Orz, I cannot find x!\n"); 78 return; 79 } 80 printf("%d\n",ans); 81 return; 82 } 83 int y,z,p; 84 int main(){ 85 int T,k; 86 T=read();k=read(); 87 int y,z,p; 88 while(T--){ 89 y=read();z=read();p=read(); 90 switch(k){ 91 case 1:{ 92 task1(y,z,p); 93 break; 94 } 95 case 2:{ 96 task2(y,z,p); 97 break; 98 } 99 case 3:{100 task3(y,z,p);101 break;102 }103 }104 }105 return 0;106 }
Bzoj2242 [SDOI2011]计算器
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。