【BZOJ2242】【SDoi2011】计算器 快速幂+EXGCD+BSGS

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

Solution:第一问快速幂

　　　　  第二问EXGCD

　　　　　　第三问BSGS

BSGS（Baby Step Giant Step）网上介绍的很详细了，但是我令x=im-j这样就不用求逆元辣，相应的为了不出现负数是i从1开始到m枚举，则j从1到m枚举，因为可以等于m，j就不需要从0开始啦.。

另：一开始在CV上测，用了puts试试，忘了自带换行在CV上过了，然而在BZOJ PE了233

 #include <iostream>
 #include <cstdio>
 #include <cmath>
 #include <map>
 #define ll long long
 using namespace std;
 ll y,z,p;

 ll fast_pow(ll y,ll z,ll p)
 {
     ll ans=;
     while (z)
     {
         if (z&)    ans=ans*y%p;
         y=y*y%p;
         z>>=;
     }
     return ans;
 }

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

 void ex_gcd(ll a,ll b,ll &x,ll &y)
 {
     if (!b) {x=;y=;return;}
     ex_gcd(b,a%b,x,y);
     ll t=x; x=y; y=t-a/b*y;
 }

 void solve1()
 {
     printf("%lld\n",fast_pow(y,z,p));
 }

 void solve2()
 {
     ll d=gcd(y,p);
     if (z%d)    {printf("Orz, I cannot find x!\n");return;}
     y/=d; z/=d;
     ll a,b;
     ex_gcd(y,p,a,b);
     a=a*z%p;
     while (a<)  a+=p;
     printf("%lld\n",a);
 }

 void solve3()
 {
     y%=p,z%=p;
     if (!y && !z)   {puts(""); return;}
     if (!y) {printf("Orz, I cannot find x!\n");return;}
     map<ll,ll> mp;
     mp.clear();
     ll m=ceil(sqrt(p));
     ll t=fast_pow(y,m,p),k=z%p;//直接m即可
     for (int i=;i<m;i++)
     {
         if (!mp[k]) if (i) mp[k]=i;//注意变量，及时订正。
                     else mp[k]=-;
         k=k*y%p;
     }
     k=;
     for (int i=;i<m;i++)
     {
         if (mp[k])//注意！mp与mp的判断
         {
             if (mp[k]==-)  mp[k]=;
             printf("%lld\n",i*m-mp[k]);
             return;
         }
         k=k*t%p;
     }
     printf("Orz, I cannot find x!\n");//各种傻
 }

 int main()
 {
     int T,t;
     scanf("%d%d",&T,&t);
     while (T--)
     {
         scanf("%lld%lld%lld",&y,&z,&p);
         if (t==)   solve1();
         if (t==)   solve2();
         if (t==)   solve3();
     }
 }