bzoj 2242: [SDOI2011]计算器

题意：

你被要求设计一个计算器完成以下三项任务：
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)的最小非负整数。

题解：

三个模板。
学了BSGS：zyf2000
code：

#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
map hash;
LL pow(LL a,LL b,LL p)
{if(a==p) return 0;LL ans=1;while(b){if(b&1) ans=ans*a%p;a=a*a%p;b>>=1;}return ans;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{if(a==0) {x=0;y=1;return b;}LL tx,ty,d=exgcd(b%a,a,tx,ty);y=tx;x=ty-(b/a)*tx;return d;
}
void solve2(LL Y,LL z,LL p)
{LL A=Y,B=p,C=z,x,y,d=exgcd(A,B,x,y);if(C%d!=0) {printf("Orz, I cannot find x!\n");return;}A/=d;B/=d;C/=d;printf("%lld\n",(x*C%B+B)%B);
}
void solve3(LL a,LL b,LL p)
{if(a%p==0) {printf("Orz, I cannot find x!\n");return;}hash.clear();LL m=ceil(sqrt(p)),a_m=pow(a,m,p),mul=b;for(LL i=0;i<=m;i++){hash[mul]=i;mul=mul*a%p;}mul=1;for(LL i=1;i<=m;i++){mul=mul*a_m%p;if(hash[mul]) {printf("%lld\n",i*m-hash[mul]);return;}}printf("Orz, I cannot find x!\n");
}
int main()
{LL T,K;scanf("%lld %lld",&T,&K);while(T--){LL y,z,p;scanf("%lld %lld %lld",&y,&z,&p);if(K==1) printf("%lld\n",pow(y,z,p));if(K==2) solve2(y,z,p);if(K==3) solve3(y,z,p);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！