Cipolla

LL ksm(LL k,LL n){    LL s=1;    for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;    return s;}namespace number{    LL D;    struct Z    {        LL x,y;        Z(LL _x=0,LL _y=0){x=_x,y=_y;}    };    Z operator +(const Z &x,const Z &y) {return Z((x.x+y.x)%mo,(x.y+y.y)%mo);}    Z operator -(const Z &x,const Z &y) {return Z((x.x-y.x+mo)%mo,(x.y-y.y+mo)%mo);}    Z operator *(const Z &x,const Z &y) {return Z((x.x*y.x%mo+D*x.y%mo*y.y%mo+mo)%mo,(x.y*y.x%mo+x.x*y.y%mo)%mo);}    Z opt(const Z &x) {return Z(mo-x.x,mo-x.y);}    Z pwr(Z k,LL n)    {        Z s=Z(1,0);        for(;n;n>>=1,k=k*k) if(n&1) s=s*k;        return s;    }}using namespace number;//其实这部分像减法，相反数什么的都没什么用...pair
    
      cipolla(LL k){    k%=mo;    if(ksm(k,(mo-1)/2)==mo-1) return make_pair(-1,-1);    if(k==0) return make_pair(0,0);    LL a=rand()%mo;    while(ksm((a*a%mo-k+mo)%mo,(mo-1)/2)<=1) a=rand()%mo;    D=(a*a%mo-k+mo)%mo;     LL v=(pwr(Z(a,1),(mo+1)/2)).x;    return make_pair(v,mo-v);}
    

BSGS

LL ds[N];int ud[N];#define mo1 10000007vector
    
      h[mo1];LL hp[mo1];int hs(LL v){    int k=v%mo1;    while(hp[k]!=-1&&hp[k]!=v) k=(k==mo1-1)?k:k+1;    return k;}void BSGS(LL x,LL a){    static LL ds2[N];    ds2[0]=ds[0]=0;    LL q=sqrt(mo);    ud[0]=0;    LL v=a;    fo(i,0,q-1)     {        int w=hs(v);        if(hp[w]==-1) ud[++ud[0]]=w,hp[w]=v;        h[w].push_back(i);        v=v*x%mo;    }    LL v2=1,vq=ksm(x,q);    for(int i=0;i-q<=mo;i+=q)    {        int w=hs(v2);        if(hp[w]!=-1)        {            int r=h[w].size();            fo(j,0,r-1) ds2[++ds2[0]]=(i-h[w][j]+mo-1)%(mo-1);        }        v2=v2*vq%mo;    }    sort(ds2+1,ds2+ds2[0]+1);    fo(i,1,ds2[0]) if(i==1||ds2[i]!=ds2[i-1]) ds[++ds[0]]=ds2[i];    fo(i,1,ud[0]) h[ud[i]].clear(),hp[ud[i]]=-1;}