2219: 数论之神 - jcvb

2219: 数论之神

jcvb posted @ 2013年12月09日 20:24 , 4542 阅读

给定奇数P,非负整数A,B。求[tex]x^A=B(\text{mod}P)[/tex]的解的数量。

分解[tex]P=\prod_{i=1}^k{ p_i}^{d_i}[/tex],化为k个模互质的方程。根据中国剩余定理,原方程的解的数量等于k个方程各自解的数量的乘积。

现在只要研究[tex]x^A=B(\text{mod}p^d)[/tex]的数量。
由于p是奇数,[tex]p^d[/tex]的原根存在,取p的某个原根g即可。
两边取指标,于是化为[tex]A\text{ind}x=\text{ind}B (\text{mod}\varphi(p^d))[/tex]
这里要用BSGS求一下[tex]\text{ind}B[/tex]。
(Upd:如果[tex]B[/tex]和[tex]p[/tex]不互质,令[tex]B=B'p^t[/tex]然后再算。。之前SB了一直没改。。。现在被插掉了。。。。。今天fix了一下)
令[tex]d=\text{gcd}(A,\varphi(p^d))[/tex],如果[tex]d|\text{ind}B[/tex]则上式有解,解的数量即为d。

/**************************************************************
    Problem: 2219
    User: jcvb
    Language: C++
    Result: Accepted
    Time:48 ms
    Memory:4840 kb
****************************************************************/
 
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define hashmod 10007
#define CNT 300000
using namespace std;
int qp(int a,int b){int ans=1;do{if(b&1)ans*=a;a*=a;}while(b>>=1);return ans;}
int qp(int a,int b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int divs[500];int dtot=0;
int proot(int p){
    dtot=0;
    int q=p-1;
    for (int i=2;i*i<=q;i++)
        if(q%i==0){
            divs[dtot++]=i;
            if(q!=i*i)divs[dtot++]=q/i;
        }
    for (int i=2;i<p;i++){
        int ok=1;
        for (int j=0;j<dtot;j++)if(qp(i,divs[j],p)==1){
            ok=0;break;
        }
        if(ok)return i;
    }
}
struct H{
    int head[hashmod];
    int S[CNT],V[CNT],next[CNT];
    int tot;
    void cl(){
        tot=0;
        memset(head,-1,sizeof(head));
    }
    int push(int s,int v){
        for (int i=head[s%hashmod];~i;i=next[i])if(S[i]==s)return V[i];
        S[tot]=s;V[tot]=v;next[tot]=head[s%hashmod];head[s%hashmod]=tot++;
        return v;
    }
}has;
              
int solve(int a,int b,int p,int al){
    int pa=qp(p,al);b%=pa;
    if(b==0){
        return qp(p,al-((al-1)/a+1));
    }else{
        int bet=0;
        while(b%p==0)b/=p,bet++;
        if(bet%a)return 0;
int tt=bet/a;
        al-=bet;
        int phi=pa-pa/p;
        int g=proot(p);
        has.cl();
        int m=int(sqrt(pa))+1;
        int gm=qp(g,m,pa);
        int cur=1;
        for (int i=1;i<=m;i++){
            cur=1ll*cur*gm%pa;
            has.push(cur,i);
        }
        cur=b;
        int ind=2000000000;
        for (int j=1;j<=m;j++){
            cur=1ll*cur*g%pa;
            int tmp;if(tmp=has.push(cur,0))ind=min(ind,tmp*m-j);
        }
        int d=gcd(a,phi);
        if(ind%d)return 0;
        return d*qp(p,(a-1)*tt);
    }
}
              
          
          
int main()
{
    int tes;
    scanf("%d",&tes);
    while(tes--){
        int a,b,k;
        scanf("%d%d%d",&a,&b,&k);k=2*k+1;
        int ans=1;
        for (int i=2;i*i<=k && ans;i++)if(k%i==0){
            int al=0;
            while(k%i==0)al++,k/=i;
            ans*=solve(a,b,i,al);
        }
        if(ans && k!=1)ans*=solve(a,b,k,1);
        printf("%d\n",ans);
    }
    return 0;
}
 
person 说:
2014年6月25日 08:27

jcvb,不知什么是两边取指标?
为什么可以从x^A变成x*indA呢,谢谢。

Avatar_small
jcvb 说:
2014年6月25日 23:06

http://wenku.baidu.com/link?url=Kjz8oD0PIZi9tAz3baEg5M1VLaFz1ofrN3wG0o6Q8fl_j7ZpE0bz0T4gjFBPT6uU8GZCazbAp5JA-8PCwu4jtR0NWiCug9M67BH8yzb4Diy

QAQ 说:
2015年2月21日 20:15

indB不一定存在

Avatar_small
jcvb 说:
2015年2月21日 20:40

@QAQ: 我错了。。

Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee