洛谷 P3846 [TJOI2007]可爱的质数 （BSGS模板题）

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll P,A,B;
map<ll,int>M;

ll mypow(ll b){
  
  ll sum=1;
  ll a=A;
  while(b){
     
    if(b&1) sum=sum*a%P;
    a=a*a%P;
    b>>=1;
  } 
  return sum;
}

int main(){
  
  scanf("%lld%lld%lld",&P,&A,&B);
  if(P%A==0){
    
    printf("no solution\n");
    return 0;
  }
  int m=(int)sqrt(P);
  ll mul=B%P;
  M[mul]=1; // B*A^0%P M[now]+=1，方便后面的判断
  for(int i=1;i<=m;i++){
    
    mul=mul*A%P;
    M[mul]=i+1; //同上
  }
  mul=mypow(m);
  ll now=1;
  bool isok=false;
  for(int i=1;i<=m;i++){
    
    now=now*mul%P;
    if(M[now]){
      
       ll ans=(ll)i*m-M[now]+1;  //M[now]-=1
       isok=true;
       printf("%lld\n",(ans%P+P)%P);
       break;
    }
  }
  if(!isok) printf("no solution\n");
  return 0;
}