解高次同余方程

/*

解高次同余方程

A^x ≡ B( mod C )

c非素数
POJ 3243
*/

#include <iostream>
#include <cstdio>
#include<cmath>
//#define maxn 65535

using namespace std;

const int maxn=65535;

struct hash
{
    int a,b,next;
}Hash[maxn*2];

int flg[maxn+66];
int top,idx;

void ins(int a,int b)
{
    int k=b&maxn;
    if(flg[k]!=idx)
    {
        flg[k]=idx;
        Hash[k].next=-1;
        Hash[k].a=a;
        Hash[k].b=b;
        return ;
    }
    while(Hash[k].next!=-1)
    {
        if(Hash[k].b==b) return ;
        k=Hash[k].next;
    }
    Hash[k].next=++top;
    Hash[top].next=-1;
    Hash[top].a=a;
    Hash[top].b=b;
}

int find(int b)
{
    int k=b&maxn;
    if(flg[k]!=idx) return -1;
    while(k!=-1)
    {
        if(Hash[k].b==b)
            return Hash[k].a;
        k=Hash[k].next;
    }
    return -1;
}

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

int exgcd(int a,int b,int& x,int& y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int r,tx,ty;
    r=exgcd(b,a%b,tx,ty);
    x=ty;
    y=tx-a/b*ty;
    return r;
}

int inval(int a,int b,int n)
{
    int x,y,e;
    exgcd(a,n,x,y);
    e=(long long )x*b%n;
    return e<0?e+n:e;
}

int pow_mod(long long a,int b,int c)
{
    long long ret=1%c;
    a%=c;
    while(b)
    {
        if(b&1)
            ret=ret*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ret;
}

int babystep(int A,int B,int C)
{
    top=maxn;++idx;
    long long buf=1%C,D=buf,K;
    int d=0,tmp;
    for(int i=0;i<=100;buf=buf*A%C,i++)
        if(buf==B)
            return i;
    while((tmp=gcd(A,C))!=1)
    {
        if(B%tmp) return -1;
        ++d;
        C/=tmp;
        B/=tmp;
        D=D*A/tmp%C;
    }
    int M=(int)ceil(sqrt((double)C)),i;
    for(buf=1%C,i=0;i<=M;buf=buf*A%C,i++) ins(i,buf);
    for(int i=0,K=pow_mod((long long)A,M,C);i<=M;D=D*K%C,i++)
    {
        tmp=inval((int)D,B,C);
        int w;
        if(tmp>=0&&(w=find(tmp))!=-1)
            return i*M+w+d;
    }
    return -1;
}

int main()
{
    int A,B,C;
    while(scanf("%d%d%d",&A,&B,&C)!=EOF,A||B||C)
    {
        B%=C;
        int tmp=babystep(A,B,C);
        if(tmp<0)
            printf("No Solution\n");
        else
            printf("%d\n",tmp);
    }
    return 0;
}

/*
解高次同余方程

A^x ≡ B( mod C )

c  是素数
时间复杂度O(sqrt(n)*logn)
POJ 2471

*/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
//快速幂求a^b
LL pow_mod(LL a,LL b,LL n)
{
    LL s=1;
    while(b)
    {
        if(b&1)
            s=(s*a)%n;
        a=(a*a)%n;
        b=b>>1;
    }
    return s;
}
//求解模方程a^x=b(mod n)。n为素数，无解返回-1
//费马小定理a^(n-1)=1(mod n),n为素数。a^0=1,所以循环节小于等于n，即如果存在解，则最小解x<=n
LL log_mod (LL a,LL b,LL n)
{
    LL m,v,e=1,i;
    m=ceil(sqrt(n+0.5));     //x=i*m+j
    //v=inv(pow_mod(a,m,n),n);  //a^m*v=1(mod n)
    v=pow_mod(a,n-m-1,n);
    map<LL,LL>x;
    x[1]=m;
    for(i=1;i<m;i++)  //建哈希表，保存x^0,x^1,...,x^m-1
    {
        e=(e*a)%n;
        if(!x[e])x[e]=i;
    }
    for(i=0;i<m;i++)//每次增加m次方，遍历所有1<=x<=n
    {
        if(x[b])
        {
            LL num=x[b];
            x.clear();//需要清空，不然会爆内存
            return i*m+(num==m?0:num);
        }
        b=(b*v)%n;   //b=b/(a^m)
    }

    return -1;
}
int main()
{
    LL a,b,n;
    while(scanf("%I64d%I64d%I64d",&n,&a,&b)!=EOF)
    {
        LL ans=log_mod(a,b,n);
        if(ans==-1)printf("no solution\n");
        else printf("%I64d\n",ans);
    }
    return 0;
}