题目：
题目链接：计算器
题解：
一道三个小函数的集合，一道板子题，写个博客记录一下，还是要先%%%%%%%hsm%%%%%%%帮我找到了错误，一定要记得是扩展BSGS（就是处理一下非素数的情况，就是除一下gcd即可），还是没好好看题啊，，(〃＞＿＜;〃)，
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL yy,z,p,n,k,a,b;
class hash
{
public:hash(){
memset(a,0xff,sizeof(a));}int locate(LL x){
LL l=x%MOD;while(a[l]!=x&&a[l]!=-1) l=(l+1)%MOD;return l;}void insert(LL x,LL va){
LL l=locate(x);if(a[l]==-1) a[l]=x,v[l]=va;}LL get(LL x) {
LL l=locate(x);return a[l]==x?v[l]:-1;}void clear(){
memset(a,0xff,sizeof(a));}private:static const LL MOD=100007;LL a[MOD+100],v[MOD+100];
}H;
LL ksm(LL a,LL b,LL mod)
{
LL s=1;while(b){
if(1&b) s=(s*a)%mod;b>>=1; a=(a*a)%mod;}return s;
}
LL exgcd1(LL a,LL b,LL &x ,LL &y)
{
LL t,s;if(!b){
x=1,y=0; return a;}s=exgcd1(b,a%b,x,y);t=x,x=y,y=t-a/b*y;return s;
}
LL Gcd(LL a,LL b){
return b?Gcd(b,a%b):a;}
void BSGS(LL yy,LL z,LL p)//扩展BSGS
{
LL d=1,y,x,m,t=1;if(yy==0&&z==0){
printf("1\n");return;}if(yy==0&&z!=0){
printf("Orz, I cannot find x!\n");return ;}H.clear();m=ceil(sqrt(double(p)));LL tmp=1,cnt=0l;LL gcd=Gcd(yy,p);while(gcd!=1)//对于非素数的处理{
if(z%gcd!=0) {
printf("Orz, I cannot find x!\n");return ;}z/=gcd; p=gcd; tmp*=(yy/gcd)%p;cnt++;}for(int i=0;i<m;i++) H.insert(t,i),t=t*yy%p;for(int i=0;i<m;i++){
exgcd1(d,p,x,y);x=((x*z)%p+p)%p; y=H.get(x);if(y!=-1) {
printf("%lld\n",i*m+y);return;}d=(d*t)%p;}printf("Orz, I cannot find x!\n");return ;
}
int main()
{
// freopen("a.txt","r",stdin);scanf("%lld%lld",&n,&k);if(k==1)//快速幂即可 {
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&yy,&z,&p);printf("%lld\n",ksm(yy,z,p));}}else if(k==2)//直接exgcd即可 {
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&yy,&z,&p);LL x,y;LL gcd=exgcd1(yy,p,x,y);if(z%gcd) puts("Orz, I cannot find x!");else{
int tm=p/gcd;while(x<0) x+=tm;printf("%lld\n",((x*z/gcd)%tm+tm)%tm);} }}else//扩展BSGS的板子即可（千万记得是扩展！！！） {
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&yy,&z,&p);BSGS(yy,z,p);}}return 0;
}