#题目描述
你被要求设计一个计算器完成以下三项任务:
- 给定\(y,z,p\),计算\(y^z \mathrm{mod} P\) 的值;
- 给定\(y,z,p\),计算满足\(xy\equiv Z ( \mathrm{mod}\ P )\)的最小非负整数;
- 给定\(y,z,p\),计算满足\(y^x\equiv Z ( \mathrm{mod}\ P )\)的最小非负整数。
#做法
- 不会的话可以退役了
- 不会的话可以退役了
- Baby Step,Giant Step
#复杂度分析
N/A
#AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
struct Op1{
long long y,z,p;
long long Pow()
{
long long ret=1;
for (;z;(y*=y)%=p,z>>=1)
if (z&1)
(ret*=y)%=p;
return ret;
}
void work()
{
scanf("%lld%lld%lld",&y,&z,&p);
printf("%lld\n",Pow());
}
};
struct Op2{
long long y,z,p;
long long aa,bb;
long long ext_gcd(long long a,long long b)
{
if (b==0)
{
aa=1;bb=1;
return a;
}
long long tt=ext_gcd(b,a%b);
long long t=aa;
aa=bb;
bb=t-a/b*bb;
return tt;
}
void work()
{
scanf("%lld%lld%lld",&y,&z,&p);
long long d=ext_gcd(y,p);
if (z%d)
{
printf("Orz, I cannot find x!\n");
return;
}
aa=aa*z/d;
aa=(aa+p)%p;
while (aa<0)
aa+=p;
printf("%lld\n",aa);
}
};
struct Op3{
long long y,z,p;
long long Pow(long long x,long long pp)
{
long long ret=1;
for (;pp;(x*=x)%=p,pp>>=1)
if (pp&1)
(ret*=x)%=p;
return ret;
}
long long Work()
{
y%=p;z%=p;
if (!y && !z)
return 1;
if (!y)
return -1;
map<long long,long long> hash;
long long m,v,e=1;
m=ceil(sqrt(p+0.5));
v=Pow(y,p-m-1);
hash[1]=m;
for (int i=1;i<m;i++)
{
(e*=y)%=p;
if (!hash[e])
hash[e]=i;
}
for (int i=0;i<m;i++)
{
if (hash[z])
{
long long num=hash[z];
hash.clear();
return i*m+(num==m?0:num);
}
(z*=v)%=p;
}
return -1;
}
void work()
{
scanf("%lld%lld%lld",&y,&z,&p);
long long ans=Work();
if (ans!=-1)
printf("%lld\n",ans);
else
printf("Orz, I cannot find x!\n");
}
};
int main()
{
Op1 a;Op2 b;Op3 c;
int t,k;
scanf("%d%d",&t,&k);
if (k==1)
while (t--)
a.work();
if (k==2)
while (t--)
b.work();
if (k==3)
while (t--)
c.work();
return 0;
}