BZOJ2219:数论之神 数论

思路:

这道题目简直就是数论合集,应用到了好多知识.

我就简单的总结一下吧.

这里有一个群\(Z^{*}_{n}\).于是,这东西叫做模\(n\)乘法群.

集合中的元素均小于\(n\)且与\(n\)互质,众所周知集合中应该有\(\phi(n)\)个元素.然后运算就是在模\(n\)意义下的乘法.

根据上述描述很容易发现这东西满足一个群的性质.

然后很显然单位元\(e=1\).

接下来介绍生成子群.

对于一个群中的某个元素\(x\),其不断利用群的运算来生成的元素集合,就是关于这个元素的生成子群,记做\(<x>\).

比如对于模\(n\)乘法群而言,\(x\)的生成子群的元素集合就应该是\(\{x,x^2,x^3,...\}\),当然这些都是在模\(n\)意义下的.

我们发现如果有一个最小的正整数\(t\)使得\(x^t=1(mod n)\),那么接下来就会有\(x^{t+1}=x^1,x^{t+2}=x^2,...\),因此我们容易发现:

\[|<x>|=t\]

现在我们考虑一个集合中的一个元素\(x\).

我们定义这个元素的阶\(ord(x)\)表示一个最小的正整数\(t\)使得\(x^t=e=1(mod n)\).显然这个正整数总是存在的.

结合刚才的说明我们得到:

\[|<x>|=ord(x)\]

然后如果某个元素\(x'\)使得\(ord(x')=\phi(n)\),我们将\(x'\)叫做\(n\)的原根.

我们不难发现\(<x'>\)和原来群的集合相等.因此\(x',x'^2,x'^3,...x'^{\phi(n)}\)恰好与所有小于\(n\)且与\(n\)互质的正整数一一对应.

以下还是将原根记做\(g\).

因此对于每一个群中的元素\(x\),我们令指标\(ind(x)\)表示\(g^{ind(x)}=x(mod n)\),其中\(1\leq{ind(x)}\leq{\phi(n)}\).

这东西显然也是存在的.

刚才算是铺垫了一些新知识吧...下面回到我们的题目.

题目是要求方程\(x^a=b(mod~p)\)在区间\([0,p-1]\)内的整数解的个数.

首先将\(p\)分解质因数,变成\(p=p_1^{q_1}p_2^{q_2}...\),随后我们依次考虑每一个\(p_i^{q_i}\).

现在方程是\(x^a=b(mod~p_i^{q_i})\),通过中国剩余定理,我们强行YY出最终的答案就是每一个方程的解的数目的乘积.

现在问题就是解这个方程了.

一种情况是:\(b=0\),围观标程发现直接返回一个奇怪的东西,目前不知道为什么.

另外一种情况是:\(b\not=1\)且\(gcd(b,p_i^{q_i})=1\),这种就非常科学.因为\(x^a\)以及\(b\)都是在模\(p_i^{q_i}\)乘法群里面的吧.

我们用一种高端方法:对于两边取指标,得到:\(a*ind(x)=ind(b)(mod\phi(p_i^{q_i}))\).

\(ind(b)\)可以用exbsgs搞出来.那么现在问题就变成了解一个线性同余方程,求解的数目.

这个我们有结论:若\(gcd(a,phi(p_i^{q_i}))|ind(b)\),则有\(gcd(a,phi(p_i^{q_i}))\)个解,否则无解.这个我先不证明了.

然后我们就解决了这种情况.

最后一种情况是:\(b\)和\(p_i^{q_i}\)不互质.这时候\(b\)显然是没有指标的.

不妨令\(b=p_i^tb'\),其中\(gcd(b',p_i)=1\).

如果\(t\%a!=0\),显然无解.

否则我们就用\(b'\)代替\(b\)来进行刚才的算法.不过最终的答案还需要乘以一个奇怪的东西.这个目前也不知道为什么.

目前好像比较科学的是这个blog:

http://www.cppblog.com/MatoNo1/archive/2013/03/15/198433.html

不过我是没有看懂= =

下面是我的代码:(求神犇出现来解决蒟蒻的两个疑问...)

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
inline int ksm(int x,int y){int r=1,t=x;for(;y;y>>=1,t*=t)if(y&1)r*=t;return r;}
inline int ksm(int x,int y,int p){int r=1,t=x;for(;y;y>>=1,t=(LL)t*t%p)if(y&1)r=(LL)r*t%p;return r;}
 
inline LL gcd(LL a,LL b){return(!b)?a:gcd(b,a%b);}
inline void exgcd(LL a,LL b,LL&d,LL&x,LL&y){if(!b)d=a,x=1,y=0;else exgcd(b,a%b,d,y,x),y-=(a/b)*x;}
inline LL solve(LL a,LL b,LL p){
    LL d,x,y;
    if(b%gcd(a,p))return-1;
    exgcd(a,p,d,x,y),x=(x%p+p)%p,x=x*b%p;
    return x;
}
 
inline int proot(int p){
    static int prime[50010];int cnt=0,tmp=p-1;
    for(int i=2;i*i<=tmp;++i){
        if(tmp%i==0){prime[++cnt]=i;while(tmp%i==0)tmp/=i;}
    }if(tmp!=1)prime[++cnt]=tmp;
    for(int i=1;i<p;++i){
        bool ok=1;
        for(int j=1;j<=cnt;++j)if(ksm(i,(p-1)/prime[j],p)==1){ok=0;break;}
        if(ok)return i;
    }
}
 
struct Hashset{
    static const int mod=13131;
    int head[mod],next[300010],f[300010],w[300010],ind;
    inline void clear(){ind=0,memset(head,-1,sizeof head);}
    inline void insert(int x,int v){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])if(f[j]==x)return;
        f[ind]=x,w[ind]=v,next[ind]=head[ins],head[ins]=ind++;
    }
    inline int operator[](const int&x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])if(f[j]==x)return w[j];
        return-1;
    }
}S;
 
inline int bsgs(int c,int a,int b,int p){
    int m=ceil(sqrt(p));
    register int i,j;
    int mi=1;for(S.clear(),i=0;i<m;++i,mi=(LL)mi*a%p)S.insert(mi,i);
    for(i=0;i*m<p;++i){
        j=S[solve((LL)c*ksm(a,i*m,p)%p,b,p)];
        if(j!=-1)return i*m+j;
    }return-1;
}
inline int exbsgs(int a,int b,int p){
    for(int i=0;i<=100;++i)if(ksm(a,i,p)==b)return i;
    int cnt=0,c=1,t;
    while((t=gcd(a,p))>1){
        if(b%t)return-1;
        b/=t,p/=t,c=(LL)c*(a/t)%p,++cnt;
    }
    int re=bsgs(c,a,b,p);
    if(re==-1)return-1;else return re+cnt;
}
 
inline int solve(int a,int b,int p,int t){
    int mi=ksm(p,t),phi=mi-mi/p;b%=mi;
    if(!b)return ksm(p,t-((t-1)/a+1));
    int d=0;while(b%p==0)b/=p,++d;
    if(d%a)return 0;
    int g=proot(p),indb=exbsgs(g,b,mi);
    if(indb==-1||indb%gcd(a,phi))return 0;else return ksm(p,d-d/a)*gcd(a,phi);
}
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
     
    int cas;scanf("%d",&cas);
    register int i,j;
    while(cas--){
        int re=1;
        int a,b,k;scanf("%d%d%d",&a,&b,&k),k=k*2+1;
        int tmp=k;
        for(i=2;i*i<=k;++i){
            int t=0;
            if(tmp%i==0){
                while(tmp%i==0)tmp/=i,++t;
                re*=solve(a,b,i,t);
            }
        }if(tmp!=1)re*=solve(a,b,tmp,1);
        printf("%d\n",re);
    }
    return 0;
}