/************************************* 求解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 100007struct 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!=-1;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!=-1;p=HashLink[p].next)    {        if( HashLink[p].key == key ) return HashLink[p].j;    }    return -1;}ll gcd(ll a,ll b){    if(b==0) return a;    return gcd(b,a%b);}//ax + by = gcd(a,b)//传入固定值a,b.放回 d=gcd(a,b), x , yvoid extendgcd(long long a,long long b,long long &d,long long &x,long long &y){    if(b==0){d=a;x=1;y=0;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=0,rey=0;    ll td=0;    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=1;    while(b)    {        if(b&1) qsum=(qsum*a)%mod;        b>>=1;        a=(a*a)%mod;    }    return qsum;}//测试x较小的情况，必须！ll firsttest(ll A,ll B,ll C){    ll tmp=1;    if(B==1) return 0;    for(int i=1;i<100;i++)    {        tmp = (tmp*A)%C;        if(tmp==B) return i;    }    return -1;}ll BabyStep(ll A,ll B,ll C,ll OC){    if(0==A || 0==C) return -1;    if(C==1) return 0;    B = B%C;    ll ans = firsttest(A,B,C);//为了防止x比较小的时候    if(ans != -1) return ans;    ll D=1;    int c=0;    ll d;    while( (d=gcd(A,C)) != 1 )    {        if( B%d !=0 ) return -1;//无解的情况        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,-1,sizeof(hashpre));    hashcnt=0;    ll hashnum=1;    hash_insert(1, 1, 0);    for(int i=1;i

 

其实这就是hdu3731了，关于思路可惜不是完全自己想的，稍微瞟了一眼大神的做法，突破了自己原先思维中不敢动c的想法，然后这题就会做了。这题A了也表示数论算是入了个门了，记得XIANBIN5在大一的时候就把数论学完了，并且把这题A了，我还是差太多啊。 接下来就是计算几何了。

以下来自:

求方程：的解个数

 

分析：设，那么上述方程解的个数就与同余方程组：的解等价。

 

设同于方程的解分别是：，那么原方程的解的个数就是

 

所以现在的关键问题是求方程：的解个数。

 

这个方程我们需要分3类讨论：

 

第一种情况：

 

对于这种情况，如果方程的某个解设为，那么一定有，可以得到，即

 

所以方程的解个数就是：，也就是

 

 

第二种情况：

 

这样也就是说p|B，设，，本方程有解的充要条件是A|t，

那么我们设t=kA，

 

所以进一步有：，因为，这样又转化为第三种情况了。

 

 

第三种情况：

 

那么我们要求指标；求指标的话又要求原根。并且奇素数p的原根也是p^a的原根，所以说求个p的原根就好了。

且如果有解，则解的个数为(A,φ(p^a))。

 

求指标的话就是要解决A^x ≡ B (mod p^a)的问题。由于本情况保证了(p^a, B)=1，用个Baby-step-Giant-step就

能解决问题。

 

方程x^A ≡ B (mod p^a)有解，当且仅当(A,φ(p^a))|ind B。ind B表示B对于p^a的任一原根的指标。