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

bzoj2242: [SDOI2011]计算器.

2024-11-22 04:41:02   202人阅读

2242: [SDOI2011]计算器

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 4353  Solved: 1679
[Submit][Status][Discuss]

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

 

1.快速幂

2.exgcd

3.bsgs

 

技术分享
  1 #include<map>  2 #include<cmath>  3 #include<cstdio>  4 using namespace std;  5 typedef long long ll;  6 map<int,int>mp;  7 inline int input() {  8     char c=getchar();int x=0,a=1;  9     for(;c<‘0‘||c>‘9‘;c=getchar()) 10         if(c==‘-‘) a=-1; 11     for(;c>=‘0‘&&c<=‘9‘;c=getchar()) 12         x=(x<<1)+(x<<3)+c-‘0‘; 13     return x*a; 14 } 15 inline ll poowmod(ll a,int k,int p) { 16     ll ret=1; 17     for(;k;k>>=1,a=(a*a)%p) 18         if(k&1) ret=(ret*a)%p; 19     return ret; 20 } 21 int gcd(int a,int b) { 22     return b==0?a:gcd(b,a%b); 23 } 24 void exgcd(int a,int b,int &x,int &y) { 25     if(b==0) { 26         x=1,y=0; 27         return; 28     } 29     exgcd(b,a%b,x,y); 30     int t=x; 31     x=y; 32     y=t-(a/b)*y; 33     return ; 34 } 35 inline void linemod(int y,int z,int p) { 36     int g=gcd(y,p),a,b; 37     if(z%g){ 38         printf("Orz, I cannot find x!\n"); 39         return; 40     } 41     y/=g; 42     z/=g; 43     p/=g; 44     exgcd(y,p,a,b); 45     a=(ll)a*z%p; 46     while(a<0) a+=p; 47     printf("%d\n",a); 48     return; 49 } 50 inline void bsgs(int y,int z,int p) { 51     mp.clear(); 52     if((y%=p)==0&&z==0) { 53         printf("1\n"); 54         return; 55     } 56     if(y==0) { 57         printf("Orz, I cannot find x!\n"); 58         return; 59     } 60     ll m=ceil(sqrt(p+0.5)); 61     mp[1]=m+1; 62     for(ll i=1,t=1;i<m;i++) { 63         t=(t*y)%p; 64         if(!mp[t]) mp[t]=i; 65     } 66     ll inv=1,tmp=poowmod(y,p-m-1,p); 67     for(ll k=0;k<m;k++,inv=(inv*tmp)%p) { 68         int i=mp[(z*inv)%p]; 69         if(i) { 70             printf("%lld\n",k*m+(i==m+1?0:i)); 71             return; 72         } 73     } 74     printf("Orz, I cannot find x!\n"); 75     return; 76 } 77 void solve(int T,int L) { 78     if(L==1) { 79         while(T--) { 80             int y=input(),z=input(),p=input(); 81             printf("%lld\n",poowmod(y,z,p)); 82         } 83     } else if(L==2) { 84         while(T--) { 85             int y=input(),z=input(),p=input(); 86             linemod(y,z,p); 87         } 88     } else { 89         while(T--) { 90             int y=input(),z=input(),p=input(); 91             bsgs(y,z,p); 92         } 93     } 94     return; 95 } 96 int main() { 97     int T=input(),L=input(); 98     solve(T,L); 99     return 0;100 }
QAQ

 

 

bzoj2242: [SDOI2011]计算器.


联系
我们