【bzoj2242】[SDOI2011]计算器

2242: [SDOI2011]计算器

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 3207 Solved: 1258
[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

【吐槽】

三合一的一道模板题。快速幂+扩展gcd+离散对数

学过这三个的人应该都会吧，不会的。。。传送门：http://www.cnblogs.com/chty/p/6022641.html

写的时候手贱把哈希表写错了，调了半天。。。

贴个丑陋的代码：

 /*************

   bzoj 2242

   by chty

   2016.11.9

 *************/

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define FILE "read"

 #define MAXN 99991

 typedef long long ll;

 struct node{ll v,f,num;}hash[MAXN+];

 ll a,b,mod;

 inline ll read()

 {

     ll x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 void insert(ll v,ll x)

 {

     ll temp=v%MAXN;

     while(hash[temp].f&&hash[temp].v!=v) {temp++; if(temp>MAXN) temp-=MAXN;}

     if(!hash[temp].f) hash[temp].f=,hash[temp].v=v,hash[temp].num=x;

 }

 ll find(ll v)

 {

     ll temp=v%MAXN;

     while(hash[temp].f&&hash[temp].v!=v) {temp++; if(temp>MAXN) temp-=MAXN;}

     if(!hash[temp].f)  return -;

     else return hash[temp].num;

 }

 ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}

 ll exgcd(ll a,ll b,ll &x,ll &y)

 {

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

     ll g=exgcd(b,a%b,x,y);

     ll t=x;x=y;y=t-a/b*y;

     return g;

 }

 void solve1(){ll sum=;for(;b;b>>=,a=a*a%mod)if(b&)sum=sum*a%mod;printf("%d\n",sum);}

 void solve2()

 {

     ll x,y,d=exgcd(a,mod,x,y);

     if(b%d)  {printf("Orz, I cannot find x!\n");return;}

     ll t=mod/d;

     while(x<)  x+=t;

     while(x>=t) x-=t;

     printf("%lld\n",x*b%mod);

 }

 void solve3()

 {

     if(mod==)  {puts(""); return;}

     a%=mod;b%=mod;

     ll ret();

     for(ll i=;i<=;i++) {if(ret==b) {printf("%lld\n",i); return; ret=ret*a%mod;}}

     ll temp,ans(),cnt();

     while((temp=gcd(a,mod))!=)

     {

         if(b%temp)  {printf("Orz, I cannot find x!\n");return;}

         mod/=temp;  b/=temp;

         ans=ans*(a/temp)%mod;

         cnt++;

     }

     ll m=(ll)sqrt(mod*1.0),t();

     for(ll i=;i<m;i++)  {insert(t,i);t=t*a%mod;}

     for(ll i=;i<m;i++)

     {

         ll x,y;

         exgcd(ans,mod,x,y);

         ll val=x*b%mod;

         val=(val+mod)%mod;

         ll j=find(val);

         if(j!=-)  {printf("%lld\n",i*m+j+cnt);return;}

         ans=ans*t%mod;

     }

     printf("Orz, I cannot find x!\n");

     return;

 }

 void pre() {for(ll i=;i<=MAXN;i++)hash[i].f=,hash[i].num=hash[i].v=-;}

 int main()

 {

     freopen(FILE".in","r",stdin);

     freopen(FILE".out","w",stdout);

     ll T=read(),flag=read();

     while(T--)

     {

         pre();

         a=read();  b=read();  mod=read();

         switch(flag)

         {

             case :solve1();break;

             case :solve2();break;

             case :solve3();break;

         }

     }

     return ;

 }

秒客网