【BZOJ 2242】[SDOI2011]计算器-白红宇

【BZOJ 2242】[SDOI2011]计算器

阅读量：6346 次

发布时间：2019-06-22

本文共 1868 字，大约阅读时间需要 6 分钟。

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】

第一问第二问略过，第三问BSGS

-------------------------------------------------------------叫我分割线-----------------------------------------------------------

什么是BSGS呢？即baby-step-giant-step，翻译成中文就是小步大步法，用于解决类似x^y=z(mod p) 求最小的y这样的问题（也许还能干别的，但本人弱渣，并不知道）

对于上面那个题目的推导

有点凌乱，等我想明白的再补

1 #include
      
        2 #define ll long long 3 #include
        4 #include
        
          5 using namespace std; 6 int T,k; 7 ll pow(ll x,int y,int p){ 8     ll ans=1; 9     while(y>0){10         if (y&1==1) ans=(ans*x)%p;11         y=y>>1;12         x=(x*x)%p;13     }14     return ans;15 }16 17 int gcd(int x,int y){18     if (x%y==0) return y;19     return gcd(y,x%y);20 }21 22 void exgcd(int a,int b,int &x,int &y){23     if (b==0){x=1,y=0;return;}24     exgcd(b,a%b,x,y);25     int t=x;x=y;y=t-(a/b)*y;26 }27 28 void solve2(int a,int z,int b){29     int tmp=gcd(a,b),x,y;30     if (z%tmp){printf("Orz, I cannot find x!\n");return;}31     exgcd(a,b,x,y);32     x=((ll)x*(z/tmp))%b;33     while (x>0) x-=b/tmp;34     while (x<0) x+=b/tmp;35     printf("%d\n",x);36 }37 38 map
         
           mp;39 void solve3(int y,int z,int p){40     y%=p;41     if (!y&&!z) {printf("1\n");return;}42     if (!y){printf("Orz, I cannot find x!\n");return;}43     mp.clear();44     ll m=ceil(sqrt(p)),t=1;45         mp[1]=m+1;//y^0==1;46     for (int i=1;i

转载于:https://www.cnblogs.com/wuminyan/p/5186862.html

你可能感兴趣的文章

java 库存进销存商户多用户管理系统 SSM springmvc 项目源码