x^a=b(mod c)求解x在[0,c-1]上解的个数模板+原根求法

/*************************************

 求解x^a=b(mod c) x在[0,c-1]上解的个数模板

 输入：1e9>=a,b>=1,1e9>=c>=3.

 返回：调用xaeqbmodc(a,b,c),返回解的个数

 复杂度: 找原根的复杂度很低，所以总的复杂度为O(c^0.5)

 ************************************/

typedef long long ll;

#define HASH_N 100007

struct hashnode

{

    int next;

    ll key;

    int j;

}HashLink[ HASH_N ];

int hashpre[ HASH_N ],hashcnt;

void hash_insert(ll x,ll key,int j)

{

    for(int p=hashpre[x];p!=-;p=HashLink[p].next)

    {

        if(HashLink[p].key==key) return ;

    }

    HashLink[ hashcnt ].key = key;

    HashLink[ hashcnt ].j = j;

    HashLink[ hashcnt ].next = hashpre[x];

    hashpre[x] = hashcnt++;

}

int hash_get(ll key)

{

    ll x=key%HASH_N;

    for(int p=hashpre[x];p!=-;p=HashLink[p].next)

    {

        if( HashLink[p].key == key ) return HashLink[p].j;

    }

    return -;

}

ll gcd(ll a,ll b)

{

    if(b==) return a;

    return gcd(b,a%b);

}

//ax + by = gcd(a,b)

//传入固定值a,b.放回 d=gcd(a,b), x , y

void extendgcd(long long a,long long b,long long &d,long long &x,long long &y)

{

    if(b==){d=a;x=;y=;return;}

    extendgcd(b,a%b,d,y,x);

    y-=x*(a/b);

}

//Ax=1(mod M)

//返回x的范围是[0,M-1]

ll GetNi(ll A,ll M)

{

    ll rex=,rey=;

    ll td=;

    extendgcd(A,M,td,rex,rey);

    return (rex%M+M)%M;

}

//a^b%mod 快速幂

long long Quk_Mul(long long a,long long b,long long mod)

{

    long long qsum=;

    while(b)

    {

        if(b&) qsum=(qsum*a)%mod;

        b>>=;

        a=(a*a)%mod;

    }

    return qsum;

}

//测试x较小的情况，必须！

ll firsttest(ll A,ll B,ll C)

{

    ll tmp=;

    if(B==) return ;

    for(int i=;i<;i++)

    {

        tmp = (tmp*A)%C;

        if(tmp==B) return i;

    }

    return -;

}

ll BabyStep(ll A,ll B,ll C,ll OC)

{

    if(==A || ==C) return -;

    if(C==) return ;

    B = B%C;

    ll ans = firsttest(A,B,C);//为了防止x比较小的时候

    if(ans != -) return ans;

    ll D=;

    int c=;

    ll d;

    while( (d=gcd(A,C)) !=  )

    {

        if( B%d != ) return -;//无解的情况

        B /= d;

        C /= d;

        D = D*A/d%C;

        c++;

    }

    //得到了 D*A^(x-c)=B (mod C) ，gcd(A,C)=1 , gcd(D,C)=1

    ll D_1=GetNi(D,C);//求D的逆元

    B = B*D_1%C;

    //求A^x=B (mod C),然后返回x+c

    ll m = ceil( sqrt(C+0.0) );

    memset(hashpre,-,sizeof(hashpre));

    hashcnt=;

    ll hashnum=;

    hash_insert(, , );

    for(int i=;i<m;i++)

    {

        hashnum = (hashnum*A)%C;

        hash_insert(hashnum%HASH_N, hashnum ,i);

    }

    ll ol=OC;//这一步可以省略

    ll mA=Quk_Mul(A, m, C);

    ll ta=;

    ll tmpni = Quk_Mul(mA, ol-, C);

    for(int i=;i<m;i++,ta=ta*tmpni%C)

    {

        //解线性同余方程 tx=B*ta (%C) ,ta直接用费马小定理求逆元

        ll tx = ta;

        tx = (tx*B)%C;

        int j=hash_get(tx);

        if(j!=-)//找到解了

        {

            return i*m+j+c;

        }

    }

    return -;

}

ll mypow(ll a,ll b)

{

    ll sum=;

    for(int i=;i<=b;i++)

        sum*=a;

    return sum;

}

ll slove(ll a,ll b,ll c,ll p,int a1)

{

    //第0种情况a==1

    if(a==) return ;

    //第一种情况b==c

    b %= c;

    if(b==)

    {

        ll tmp = mypow(p,ceil( (double)a1/a ) );

        return c/tmp;

    }

    ll d=gcd(b,c);

    //第二种情况 gcd(b,c)!=1

    if( d !=  )

    {

        return ;

    }

    //第三种情况 gcd(b,c)==1

    //第一步找出原根x0,

    ll save[];

    int cnt=;

    ll tc = mypow(p,a1-)*(p-);

    for(ll i=;i*i<=tc;i++)

    {

        if(tc%i == )

        {

            save[ cnt++ ] = i;

            while(tc%i==) tc/=i;

        }

    }

    if(tc != )

    {

        save[ cnt++ ] = tc;

    }

    tc= mypow(p,a1-)*(p-);

    for(int i=;i<cnt;i++)

    {

        save[i] = tc/save[i];

    }

    ll x0=;

    for(int i=;i<c;i++)

    {

        int flag=;

        for(int j=;j<cnt;j++)

        {

            if( Quk_Mul(i, save[j], c) ==)

            {

                flag=;

                break;

            }

        }

        if(flag==)

        {

            x0=i;

            break;

        }

    }

    //找到原根x0后,然后找x0^a0 = b (mod c)

    ll a0 = BabyStep(x0 , b, c,mypow(p,a1-)*(p-));

    ll ord = mypow(p,a1-)*(p-);

    d = gcd(a,ord);

    if( a0%d !=  ) return ;

    return d;

}

ll xaeqbmodc(ll a,ll b,ll c)

{

    ll ans=;

    b%=c;

    ll tc=c;

    //然后对c进行因式分解

    for(ll i=;i*i<=tc;i++)

    {

        if(tc%i==)

        {

            ll tmpyz=;

            int a1=;

            while(tc%i==)

            {

                a1++;

                tmpyz *= i;

                tc/=i;

            }

            //然后对这个因子进行处理

            ans *= slove(a,b,tmpyz,i,a1);

            if(ans==) break;

        }

    }

    if(tc!=)

    {

        ans *= slove(a,b,tc,tc,);

    }

    return ans;

}