洛咕
题意:给定y,z,p,有三种操作:
1、计算y^z mod p的值;
2、计算满足x*y≡z(mod p)的最小非负整数x;
3、计算满足y^x≡z(mod p)的最小非负整数x;
分析:模板题.快速幂+扩欧+BSGS.
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
LL ksm(LL a,LL b,LL p){
LL cnt=1;
while(b){
if(b&1)cnt=(LL)(cnt*a)%p;
a=(LL)(a*a)%p;
b>>=1;
}
return cnt;
}
LL exgcd(LL a,LL b,LL &x,LL &y){
if(b==0){x=1;y=0; return a;}
LL d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
LL BSGS(LL a,LL b,LL p){
map<LL,LL>hash;hash.clear();
b%=p;int t=(int)sqrt(p)+1;
for(int j=0;j<t;j++){
int val=(LL)b*ksm(a,j,p)%p;
hash[val]=j;
}
a=ksm(a,t,p);
if(a==0)return b==0?1:-1;
for(int i=0;i<=t;i++){
int val=ksm(a,i,p);
int j=hash.find(val)==hash.end()?-1:hash[val];
if(j>=0&&i*t-j>=0)return i*t-j;
}
return -1;
}
int main(){
LL T=read(),k=read();
while(T--){
LL y=read(),z=read(),p=read();
if(k==1)printf("%lld
",ksm(y,z,p));
//操作1,直接快速幂输出答案
else if(k==2){
LL x=0,yy=0,gcd=exgcd(y,p,x,yy);
if(z%gcd==0){//如果有解
LL tmp=p/gcd;
x=(((x*z)/gcd)%tmp+tmp)%tmp; //找到最小解
printf("%lld
",x);
}
else printf("Orz, I cannot find x!
");
}
else if(k==3){
LL ans=BSGS(y,z,p);
if(ans==-1)printf("Orz, I cannot find x!
");
else printf("%lld
",ans);
}
}
return 0;
}
超级快的链式前向星哈希,但在正确率上有点BUG,不过洛咕还是能过的.
#include<bits/stdc++.h>
#define LL long long
#define LB long double
using namespace std;
inline LL read(){
LL s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int top,tou[376637];
struct ppx{
int p,x;LL y;
}b[376637],c;
inline LL ksm(LL a,LL b,LL c){
LL cnt=1;
while(b){
if(b&1)cnt=(LL)(cnt*a)%c;
a=(LL)(a*a)%c;
b>>=1;
}
return cnt;
}
inline LL exgcd(LL a,LL b,LL &x,LL &y){
if(b==0){x=1;y=0;return a;}
LL d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
inline LL ksc(LL x,LL y,LL p){
return (x*y-(LL)((LB)x/p*y)*p+p)%p;
}
inline void ha1(int x,LL y){
b[++top].x=x;b[top].y=y;y%=376637;
b[top].p=tou[y]; tou[y]=top;
}
inline LL BSGS(int x,LL y,LL p){
for(int i=0;i<372637;++i)b[i]=c,tou[i]=0,top=0;
int z=pow(p,0.5)+1;
LL sx=1,sy=1;
for(int i=0;i<z;++i,sx=ksc(sx,x,p))
ha1(i,ksc(sx,y,p));
sy=sx;
for(int i=1;i<=z;++i,sy=ksc(sy,sx,p)){
for(int j=tou[sy%376637];j;j=b[j].p)
if(sy==b[j].y)return (LL)i*z-b[j].x;
}return -1;
}
int main(){
int T=read(),K=read();
while(T--){
int y=read(),z=read(),p=read();
if(K==1)printf("%lld
",ksm(y,z,p));
else if(K==2){
LL x,y0,d=exgcd(y,p,x,y0);
if(z%d)printf("Orz, I cannot find x!
");
else printf("%lld
",((x*z/d)%(p/d)+(p/d))%(p/d));
}
else if(K==3){
if(y%p==0&&z!=0){
puts("Orz, I cannot find x!");
continue;
}
int ans=BSGS(y,z,p);
if(ans!=-1)printf("%d
",ans);
else puts("Orz, I cannot find x!");
}
}
return 0;
}