【BZOJ2242】计算器（BSGS，快速幂）

题面

BZOJ

洛谷

1、给定y、z、p，计算y^z mod p 的值；

2、给定y、z、p，计算满足xy ≡z(mod p)的最小非负整数x；

3、给定y、z、p，计算满足y^x ≡z(mod p)的最小非负整数x。

题解

第一问是裸的快速幂

第二问，因为\(P\)是质数，所以求一下乘法逆元再乘\(z\)就行了，特判\(y\)是\(p\)的倍数时无解

第三问，\(bsgs\)模板

洛谷上的时间：

\(map:652ms\)

\(Hash:48ms\)

。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
const int HashMod=100007;
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int fpow(int a,int b,int MOD)
{
int s=1;
while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}
return s;
}
void NoAnswer(){puts("Orz, I cannot find x!");}
namespace Task1{void Solve(int y,int z,int p){printf("%d\n",fpow(y,z,p));}}
namespace Task2
{
void Solve(int y,int z,int p)
{
if(y%p==0&&z%p)NoAnswer();
else printf("%lld\n",1ll*fpow(y,p-2,p)*z%p);
}
}
namespace Task3
{
struct HashTable
{
struct Line{int u,v,next;}e[1000000];
int h[HashMod],cnt;
void Add(int u,int v,int w){e[++cnt]=(Line){w,v,h[u]};h[u]=cnt;}
void Clear(){memset(h,0,sizeof(h));cnt=0;}
void Hash(int x,int k)
{
int s=x%HashMod;
Add(s,k,x);
}
int Query(int x)
{
int s=x%HashMod;
for(int i=h[s];i;i=e[i].next)
if(e[i].u==x)return e[i].v;
return -1;
}
}Hash;
void Solve(int y,int z,int p)
{
if(y%p==0){NoAnswer();return;}
y%=p;z%=p;
if(z==1){puts("0");return;}
int m=sqrt(p)+1;Hash.Clear();
for(RG int i=0,t=z;i<m;++i,t=1ll*t*y%p)Hash.Hash(t,i);
for(RG int i=1,tt=fpow(y,m,p),t=tt;i<=m+1;++i,t=1ll*t*tt%p)
{
int k=Hash.Query(t);if(k==-1)continue;
printf("%d\n",i*m-k);return;
}
NoAnswer();
}
}
int main()
{
int T=read(),K=read();
while(T--)
{
int y=read(),z=read(),p=read();
if(K==1)Task1::Solve(y,z,p);
if(K==2)Task2::Solve(y,z,p);
if(K==3)Task3::Solve(y,z,p);
}
return 0;
}