BZOJ2242 [SDOI2011]计算器

2022-12-21 07:47:50

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000

作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

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

正解：快速幂+exgcd+BSGS

解题报告：

　　快速幂+exgcd+BSGS。

　　有一些细节。exgcd都快忘了......

　　学习BSGS戳这里：http://www.cnblogs.com/ljh2000-jump/p/6230999.html

 //It is made by ljh2000

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 #include <string>

 using namespace std;

 typedef long long LL;

 const int MOD = ;

 const int MAXM = ;

 int k,p,first[MOD+],ecnt,to[MAXM],w[MAXM],next[MAXM],m,ans;

 inline int gcd(int x,int y){ if(y==) return x; return gcd(y,x%y); }

 inline int fast_pow(LL x,int y){ LL r=; while(y>) { if(y&) r*=x,r%=p; x*=x; x%=p; y>>=;  } return (int)r; }

 inline void wujie(){ printf("Orz, I cannot find x!"); }

 inline int getint(){

     int w=,q=; char c=getchar(); while((c<''||c>'') && c!='-') c=getchar();

     if(c=='-') q=,c=getchar(); while (c>=''&&c<='') w=w*+c-'',c=getchar(); return q?-w:w;

 }

 inline void exgcd(LL x,LL y,LL &d,LL &a,LL &b){

     if(y==) { d=x; a=; b=; return ; }

     exgcd(y,x%y,d,b,a);

     b-=x/y*a;

 }

 inline void solve(int a,int Z){

     int GCD=gcd(a,p); if(Z%GCD!=) { wujie(); return ; }

     LL x,y,GG; exgcd((LL)a,(LL)p,GG,x,y);

     Z/=GCD; p/=GCD;

     ans=Z*x%p; ans+=p; ans%=p;

     printf("%d",ans);

 }

 inline void insert(int x,int j){

     int cc=x; x%=MOD; for(int i=first[x];i;i=next[i]) if(to[i]==cc) { w[i]=j; return ;}

     next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=cc; w[ecnt]=j;

 }

 inline int query(int x){

     int cc=x; x%=MOD; for(int i=first[x];i;i=next[i]) if(to[i]==cc) return w[i];

     return -;

 }

 inline void BSGS(int a,int b){

     if(a%p==) { wujie(); return; }

     //if(b==1) { printf("0"); return ; }

     ecnt=; memset(first,,sizeof(first));

     m=sqrt(p); if(m*m<p) m++; LL cc=b; insert(b,);

     for(int i=;i<=m;i++) cc*=a,cc%=p,insert((int)cc,i);

     cc=; LL cun=fast_pow(a,m);

     for(int i=;i<=m;i++) {

         cc*=cun; cc%=p;    ans=query(cc);

         if(ans==-) continue;

         printf("%d",i*m-ans);

         return ;

     }

     wujie();

 }

 inline void work(){

     int T=getint(); k=getint(); int x,y;

     while(T--) {

         x=getint(); y=getint(); p=getint();

         if(k==) printf("%d",fast_pow(x,y));

         else if(k==) solve(x,y);

         else BSGS(x,y);

         printf("\n");

     }

 }

 int main()

 {

     work();

     return ;

 }

码农公寓