首页 > 代码库 > BZOJ2480: Spoj3105 Mod

BZOJ2480: Spoj3105 Mod

    已知数a,p,b,求满足a^x≡b(mod p)的最小自然数x。p不一定是素数。

    先附上AekdyCoin大牛的题解:http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4

    然后我们来证明算法的正确性。

    不妨认为我们消因子后,a->a,b->b‘,c->c‘,d,e(指文中的D),除去的gcd之积为f,且(a,c‘)=1

    那么其实 a^d=f*e,然后我们用BSGS求解 e*a^x=b‘ mod c‘ 因为(a,c‘)=1

    而且x就是(a^inf,c)

    然后假设我们得到了一个解  e*a^x=b‘ mod c‘ 考虑回推出原同余方程的解。

    由裴蜀定理值存在唯一的  e*a^x+c‘*y=b‘  (注意现在是等号,而不是模意义)

    我们在等式两边乘以f,就得到了 a^d*a^x+c*y=b ,也就是a^(d+x)=b mod c,这说明x+d是原方程的解。

    我知道公式写成这样是没人耐心看的

    还是看代码比较亲切

    

map<int,int>mp;inline int gcd(int x,int y){return y?gcd(y,x%y):x;}inline int power(int x,int y,int p){    int t=1;    for(;y;y>>=1,x=(ll)x*x%p)     if(y&1)t=(ll)t*x%p;    return t;}inline int solve(int a,int b,int c){    a%=c;b%=c;    for(int i=0,j=1;i<=50;i++,j=(ll)j*a%c)if(j==b)return i;    int d=0,e=1%c,t;    while((t=gcd(a,c))!=1)    {            if(b%t)return -1;        c/=t;b/=t;d++;e=(ll)e*a/t%c;    }    mp.clear();    int m=ceil(sqrt(c));    for(int i=0,j=1;i<m;i++,j=(ll)j*a%c)mp[(ll)b*j%c]=i;    a=power(a,m,c);    for(int i=0,j=e;i<=m;i++,j=(ll)j*a%c)     if(i&&mp.find(j)!=mp.end())       return  i*m-mp[j]+d;    return -1;}int main(){    freopen("input.txt","r",stdin);    freopen("output.txt","w",stdout);    while(1)    {        int a=read(),c=read(),b=read(),t;        if(!(a||b||c))break;        if((t=solve(a,b,c))>=0)printf("%d\n",t);        else printf("No Solution\n");    }    return 0;}

 

     

BZOJ2480: Spoj3105 Mod