首页 > 代码库 > BZOJ2242: [SDOI2011]计算器

BZOJ2242: [SDOI2011]计算器

2024-07-21 13:37:32   215人阅读

2242: [SDOI2011]计算器

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 1278  Solved: 492
[Submit][Status]

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。

Sample Output

【样例输出1】
2
1
2
【样例输出2】
2
1
0

HINT

 

Source

第一轮day1

题解：
第一问快速幂，第二问拓展欧几里德，第三问shank的大步小步算法。
算法基于这样的性质：
若有 a^(k*m+i)=b (mod p)
则有 a^i=b/(a^km) =b*(a^km)-1  (mod p) 其中-1 指 模p意义下的逆元
如果 左边的i很少，我们就可以预处理出所有的 a^i，然后枚举k查询是否有 b*(a^km)-1这样的键值存在，存在的话答案就是 k*m+i.
显然 m取sqrt（n）比较合适。
枚举k时还有技巧就是a^km的逆元随着k的增加，不用每次都求，我们先求出a^m的逆元 t=power（a,p-m-1,p）
这样每次k++，b*=t,这是因为 a^(p-m-1+p-m-1)=a^(p-2*m-1)*a^(p-1)=a^(p-m-1)。
查询可以用map存储，也可以手写二分。
bzoj的评测机太感人了，本地测50s+，在bzoj上居然1s就跑出来了，真是奇迹。
代码：
  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 500+100 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long  17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 using namespace std; 22 typedef map<int,int>::const_iterator cit; 23 typedef map<int,int>::value_type vt;  24 map<int,int> mp; 25 inline ll read() 26 { 27     int x=0,f=1;char ch=getchar(); 28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30     return x*f; 31 } 32 ll a,b,p,x,y,t,tt,gcd,m,cs,ch; 33 ll work1(ll a,ll b,ll p) 34 { 35     ll ans=1; 36     for(;b;b>>=1,a*=a,a%=p) 37      if(b&1)ans*=a,ans%=p; 38     return ans;  39 } 40 void exgcd(ll a,ll b) 41 { 42     if(!b){x=1;y=0;gcd=a;} 43     else 44      { 45          exgcd(b,a%b); 46          t=x;x=y;y=t-(a/b)*y; 47      } 48 } 49 void work2() 50 { 51     exgcd(a,p); 52     if(b%gcd)puts("Orz, I cannot find x!"); 53     else 54      { 55          x*=b/gcd;y*=b/gcd; 56         t=p/gcd; 57          x=(x%t+t)%t; 58          printf("%lld\n",x); 59      } 60 } 61 void work3() 62 { 63     a%=p;b%=p; 64     if(!a&&!b){printf("1\n");return;} 65     if(!a){puts("Orz, I cannot find x!");return;} 66     m=floor(sqrt(p)); 67     mp.clear(); 68     mp.insert(mp.begin(),vt(1,0)); 69     t=1; 70     for1(i,m-1)t*=a,t%=p,mp.insert(mp.begin(),vt(t,i)); 71     t=work1(a,p-m-1,p); 72     for0(i,p/m) 73      { 74          cit j=mp.find(b); 75          if(j!=mp.end()) 76          { 77             printf("%lld\n",j->second+i*m); 78              return; 79          } 80         b*=t;b%=p;  81      } 82      puts("Orz, I cannot find x!"); 83 } 84 int main() 85 { 86     freopen("input.txt","r",stdin); 87     freopen("output.txt","w",stdout); 88     cs=read();ch=read(); 89     while(cs--) 90      { 91          a=read();b=read();p=read(); 92          switch(ch) 93          { 94              case 1:printf("%lld\n",work1(a,b,p));break; 95              case 2:work2();break; 96              case 3:work3();break; 97          } 98      } 99     return 0;100 }
View Code

 

BZOJ2242: [SDOI2011]计算器


联系
我们