BZOJ 2242 计算器
你被要求设计一个计算器完成以下三项任务:
- 给定y,z,p,计算$y^z\mod p$ 的值;
- 给定y,z,p,计算满足$xy \equiv z(\mod p)$的最小非负整数;
- 给定y,z,p,计算满足$y^x \equiv z (\mod p)$的最小非负整数。
其中p为质数,$y,z,p\le 10^9$
题解
任务一裸快速幂不解释。
任务二显然$x=\frac{z}{y}=z\times y^{-1}$,根据费马小定理$y^{-1}\equiv y^{p-2}(\mod p)$,所以$x\equiv z\times y^{p-2}$,非常显然。
任务三为BSGS。
求$y^x\equiv z(\mod p)$的最小非负整数解。
显然根据费马小定理,$y^{x+(p-1)}\equiv y^x$
所以$0\le x<p-1$
设$x=im-j$,其中$1\le j \le m,1\le i \le \lceil \frac{p}{m}\rceil$,这样即可满足$0\le im-j \le \lceil \frac{p}{m}\rceil m-1$,显然$\lceil \frac{p}{m}\rceil m-1 \ge p-1$,所以显然可以。
则$y^{im-j}\equiv z$,所以$y^{im}\equiv zy^{j}$,所以
$(y^m)^i \equiv zy^j$
所以我们先把$zy^{1},zy^{2}\dots zy^{m}$存进哈希表/map
然后在用$(y^m)^1,(y^m)^2\dots (y^m)^{\lceil \frac{p}{m}\rceil}$依次查询。
如果$(y^m)^i$查到了,并且查到的对应的是$zy^j$,那么答案就是$x=im-j$,找到答案以后就退出。
时间复杂度$O(m+\frac{p}{m})$,当$m=\sqrt{p}$时取得最小值$O(\sqrt{p})$
/*
Author: CNYALI_LK
LANG: C++
PROG: 2242.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll fpm(ll a,ll b,ll p){
ll c=1;
a%=p;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
namespace cheat1{
ll f(ll a,ll b,ll p){
return fpm(a,b,p);
}
void js(ll t){
ll y,z,p;
while(t){
--t;
scanf("%lld%lld%lld",&y,&z,&p);
printf("%lld\n",f(y,z,p));
}
}
}
namespace cheat2{
ll f(ll a,ll b,ll p){
a%=p;b%=p;
if(!b)return 0;
if(!a)return -1;
return b*fpm(a,p-2,p)%p;
}
void js(ll t){
ll y,z,p;
while(t){
--t;
scanf("%lld%lld%lld",&y,&z,&p);
ll s=f(y,z,p);
if(s+1)printf("%lld\n",s);
else printf("Orz, I cannot find x!\n");
}
}
}
namespace cheat3{
ll f(ll a,ll b,ll p){
a%=p;b%=p;
if(!a&&!b)return 0;
if(!a)return -1;
tr1::unordered_map<ll,ll> mp;
ll m=(ll)ceil(sqrt((long double)p));
ll x=b;
for(ll i=1;i<=m;++i){
x=x*a%p;
mp.insert(make_pair(x,i));
}
b=1;
for(ll i=0;i<m;++i)b=b*a%p;
x=1;
for(ll i=1;i<=m;++i){
x=x*b%p;
if(mp[x])return i*m-mp[x];
}
return -1;
}
void js(ll t){
ll y,z,p,s;
while(t){
--t;
scanf("%lld%lld%lld",&y,&z,&p);
s=f(y,z,p);
if(s+1)printf("%lld\n",s);
else printf("Orz, I cannot find x!\n");
}
}
}
int main(){
#ifdef cnyali_lk
freopen("2242.in","r",stdin);
freopen("2242.out","w",stdout);
#endif
ll t,k;
scanf("%lld%lld",&t,&k);
if(k==1)cheat1::js(t);
else if(k==2)cheat2::js(t);
else cheat3::js(t);
return 0;
}