[文章目录]
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)的最小非负整数。
1<=y,z,p<=10^9，为质数，1<=T<=10。
注意这不是亦或，是幂次。
1.快速幂啊，233
2.转化为xy+kp=z，显然extgcd，不过有个限定就是k<0。借鉴黄学长的方法，p=-p。然后再求。但是发现gcd为-，然后除完又变成正的。ans最后输出总为负。没办法，特判了一下。
3.早上看的题解，上午PoPoQQQ就讲了，哇，好开心（叫什么小步大步baby step giant step还有什么双向广搜meet in the middle，个人感觉就是分块）。
幂次肯定不超过p-1对吧【费马小定理】。考虑将幂次分解x=i*m+j。
=>y^(i*m+j)=z (%p)
=>y^j=zy^(p-1-im) (%p) [ a^φ(p)≡1 (mod p&&gcd(a,p)==1) ]
所以，对于每一个i，我们求出来式子的右面，左面预处理出来，扔到哈希表里【然而这是个毛??算了，就当是map吧】，O(1)查询左面的是否存在，若存在一个j满足，那么i*m+j就是一个解。如果i从小开始枚举的话就是最小解了。然后嘛，m取√p的时候比较优秀。时间复杂度√p级别。好像还有什么特判什么的。
还有 一个重要的事情 ：
%%%PoPoQQQ
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll T,k,ans1,ans2,y,z,p;
map<ll,ll>v;
ll extgcd(ll a,ll b)
{
if(b==0)
{
ans1=1;ans2=0;return a;
}
ll tmp=extgcd(b,a%b);
ll t=ans1; ans1=ans2; ans2=t-a/b*ans2;
return tmp;
}
ll pow(ll x,ll t)
{
ll re=1;
while(t)
{
if(t&1) re=re*x%p;
x=x*x%p; t>>=1;
}
return re;
}
int main()
{
scanf("%lld%lld",&T,&k);
if(k==1)
{
while(T--)
{
scanf("%lld%lld%lld",&y,&z,&p);
y%=p; printf("%lld\n",pow(y,z));
}
}
if(k==2)
{
while(T--)
{
scanf("%lld%lld%lld",&y,&z,&p);
p=-p; ll tmp=extgcd(y,p); p/=tmp;
if(z%tmp) puts("Orz, I cannot find x!");
else
{
z/=tmp;
ans1=ans1*z%p;
if(p<0) p=-p;
printf("%lld\n",(ans1%p+p)%p);
}
}
}
if(k==3)
{
while(T--)
{
scanf("%lld%lld%lld",&y,&z,&p); y%=p;
ll m=sqrt(p),tmp=1; v.clear();
if(!y&&!z){puts("1");continue;}
if(!y){puts("Orz, I cannot find x!");continue;}
for(ll i=0;i<m;i++)
{
if(v.find(tmp)==v.end()) v[tmp]=i;
tmp=tmp*y%p;
}
bool flag=1;
ll ine=pow(y,p-m-1); tmp=z;
for(ll i=0;i<p;i+=m)
{
if(v.find(tmp)!=v.end())
{
printf("%lld\n",i+v[tmp]);
flag=0;
break;
}
tmp=tmp*ine%p;
}
if(flag) puts("Orz, I cannot find x!");
}
}
return 0;
}