高次同余方程

详解
下面的模板中是，调用函数时是A,B,C A^x=B(mod C)
poj3243(模板题)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long LL;
struct HashMap
{//哈希表
    static const int Hash=999917,maxn=46340;
    int num,link[Hash],son[maxn+5],next[maxn+5],w[maxn+5];
    int top,Stack[maxn+5];
    void clear()
    {//清空表
        num=0;
        while(top)
            link[Stack[top--]]=0;
    }
    void add(int x,int y)
    {//添加键值元素
        son[++num]=y;
        next[num]=link[x];
        w[num]=INF;
        link[x]=num;
    }
    bool count(int y)
    {//判断表中是否有对应值
        int x=y%Hash;
        for(int j=link[x];j;j=next[j])
            if(y==son[j])
                return true;
        return false;
    }
    int &operator [](int y)
    {//获取键的对应值
        int x=y%Hash;
        for(int j=link[x];j;j=next[j])
            if(y==son[j])
                return w[j];
        add(x,y);
        Stack[++top]=x;
        return w[num];
    }
}hashMap;
int GCD(int a,int b)
{
    if(b==0)
        return a;
    return GCD(b,a%b);
}
int extendedGCD(int x,int y,int &a,int &b)
{
    if(y==0)
    {
        a=1;
        b=0;
        return x;
    }
    int temp;
    int gcd=extendedGCD(y,x%y,a,b);
    temp=a;
    a=b;
    b=temp-x/y*b;
    return gcd;
}
int extendBSGS(int A,int B,int C)
{
    //三种特判
    if(C==1)
    {
        if(!B)
            return A!=1;
        return -1;
    }
    if(B==1)
    {
        if(A)
            return 0;
        return -1;
    }
    if(A%C==0)
    {
        if(!B)
            return 1;
        return -1;
    }

    int gcd=GCD(A,C);
    int D=1,num=0;
    while(gcd!=1)
    {//把A,C变成(A,C)=1为止
        if(B%gcd)
            return -1;
        B/=gcd;//从B中约去因子
        C/=gcd;//约C中约去因子
        D=((LL)D*A/gcd)%C;//将多出的乘给D
        num++;//统计约去次数
        gcd=GCD(A,C);
    }
    int now=1;
    for(int i=0;i<=num-1;i++){//枚举0~num-1
        if(now==B)
            return i;
        now=((LL)now*A)%C;
    }
    hashMap.clear();
    int Size=ceil(sqrt(C)),Base=1;
    for(int i=0;i<=Size-1;i++)
    {//将A^j存进哈希表
        hashMap[Base]=min(hashMap[Base],i);//存储答案最小的
        Base=((LL)Base*A)%C;
    }
    for(int i=0;i<=Size-1;i++)
    {//扩展欧几里得求A^j
        int x,y;
        int gcd=extendedGCD(D,C,x,y);//求出x、y
        x=((LL)x*B%C+C)%C;
        if(hashMap.count(x))
            return i*Size+hashMap[x]+num;//加回num
        D=((LL)D*Base)%C;
    }
    return -1;//无解
}
int main()
{
    int X,K,Z;
    while(scanf("%d%d%d",&X,&Z,&K)!=EOF&&(X+Z+K)){
        int res=extendBSGS(X,K,Z);
        if(res==-1)
            printf("No Solution\n");
        else
            printf("%d\n",res);
    }
    return 0;
}

poj2417(套模板)
注意输入顺序

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long LL;
struct HashMap
{//哈希表
    static const int Hash=999917,maxn=46340;
    int num,link[Hash],son[maxn+5],next[maxn+5],w[maxn+5];
    int top,Stack[maxn+5];
    void clear()
    {//清空表
        num=0;
        while(top)
            link[Stack[top--]]=0;
    }
    void add(int x,int y)
    {//添加键值元素
        son[++num]=y;
        next[num]=link[x];
        w[num]=INF;
        link[x]=num;
    }
    bool count(int y)
    {//判断表中是否有对应值
        int x=y%Hash;
        for(int j=link[x];j;j=next[j])
            if(y==son[j])
                return true;
        return false;
    }
    int &operator [](int y)
    {//获取键的对应值
        int x=y%Hash;
        for(int j=link[x];j;j=next[j])
            if(y==son[j])
                return w[j];
        add(x,y);
        Stack[++top]=x;
        return w[num];
    }
}hashMap;
int GCD(int a,int b)
{
    if(b==0)
        return a;
    return GCD(b,a%b);
}
int extendedGCD(int x,int y,int &a,int &b)
{
    if(y==0)
    {
        a=1;
        b=0;
        return x;
    }
    int temp;
    int gcd=extendedGCD(y,x%y,a,b);
    temp=a;
    a=b;
    b=temp-x/y*b;
    return gcd;
}
int extendBSGS(int A,int B,int C)
{
    //三种特判
    if(C==1)
    {
        if(!B)
            return A!=1;
        return -1;
    }
    if(B==1)
    {
        if(A)
            return 0;
        return -1;
    }
    if(A%C==0)
    {
        if(!B)
            return 1;
        return -1;
    }

    int gcd=GCD(A,C);
    int D=1,num=0;
    while(gcd!=1)
    {//把A,C变成(A,C)=1为止
        if(B%gcd)
            return -1;
        B/=gcd;//从B中约去因子
        C/=gcd;//约C中约去因子
        D=((LL)D*A/gcd)%C;//将多出的乘给D
        num++;//统计约去次数
        gcd=GCD(A,C);
    }
    int now=1;
    for(int i=0;i<=num-1;i++){//枚举0~num-1
        if(now==B)
            return i;
        now=((LL)now*A)%C;
    }
    hashMap.clear();
    int Size=ceil(sqrt(C)),Base=1;
    for(int i=0;i<=Size-1;i++)
    {//将A^j存进哈希表
        hashMap[Base]=min(hashMap[Base],i);//存储答案最小的
        Base=((LL)Base*A)%C;
    }
    for(int i=0;i<=Size-1;i++)
    {//扩展欧几里得求A^j
        int x,y;
        int gcd=extendedGCD(D,C,x,y);//求出x、y
        x=((LL)x*B%C+C)%C;
        if(hashMap.count(x))
            return i*Size+hashMap[x]+num;//加回num
        D=((LL)D*Base)%C;
    }
    return -1;//无解
}
int main()
{
    int P,B,N;
    while(scanf("%d%d%d",&P,&B,&N)!=EOF)
    {
        int res=extendBSGS(B,N,P);
        if(res==-1)
            printf("no solution\n");
        else
            printf("%d\n",res);
    }
    return 0;
}

hdu 2815
换了一个模板，之前的那个，可能是数据范围的原因，一直WA。
关键还是建立方程，直接套模板即可。

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int MAXN=131071;
struct HashNode
{
    ll data, id, next;
};
HashNode hash[MAXN<<1];
bool flag[MAXN<<1];
ll top;
void Insert (ll a,ll b )
{
    ll k=b&MAXN;
    if (flag[k]==false)
    {
        flag[k]=true;
        hash[k].next=-1;
        hash[k].id=a;
        hash[k].data=b;
        return;
    }
    while(hash[k].next!=-1)
    {
        if(hash[k].data==b)
            return;
        k=hash[k].next;
    }
    if(hash[k].data==b)
        return;
    hash[k].next=++top;
    hash[top].next=-1;
    hash[top].id=a;
    hash[top].data=b;
}
ll Find(ll b)
{
    ll k=b&MAXN;
    if(flag[k]==false)
        return -1;
    while(k!=-1)
    {
        if(hash[k].data==b)
            return hash[k].id;
        k=hash[k].next;
    }
    return -1;
}
ll gcd(ll a,ll b)
{
    return b?gcd (b,a%b):a;
}
ll ext_gcd(ll a,ll b,ll& x,ll& y )
{
    ll t,ret;
    if (b==0)
    {
        x=1,y=0;
        return a;
    }
    ret=ext_gcd(b,a%b,x,y);
    t=x,x=y,y=t-a/b*y;
    return ret;
}
ll mod_exp(ll a,ll b,ll n )
{
    ll ret=1;
    a=a%n;
    while(b>=1)
    {
        if(b&1)
            ret=ret*a%n;
        a=a*a%n;
        b>>=1;
    }
    return ret;
}
ll BabyStep_GiantStep(ll A,ll B,ll C)
{
    top=MAXN;
    B%=C;
    ll tmp=1,i;
    for(i=0;i<=100;tmp=tmp*A%C,i++)
        if (tmp==B%C)
            return i;
    ll D=1,cnt=0;
    while((tmp=gcd(A,C))!=1 )
    {
        if(B%tmp)
            return -1;
        C/=tmp;
        B/=tmp;
        D=D*A/tmp%C;
        cnt++;
    }
    ll M=(ll)ceil(sqrt(C+0.0));
    for (tmp=1,i=0;i<=M;tmp=tmp*A%C,i++)
        Insert(i,tmp);
    ll x,y,K=mod_exp(A,M,C);
    for(i=0;i<=M;i++)
    {
        ext_gcd(D,C,x,y); // D * X = 1 ( mod C )
        tmp=((B*x)%C+C)%C;
        if((y=Find(tmp))!=-1)
            return i * M + y + cnt;
        D=D*K%C;
    }
    return -1;
}
int main()
{
    ll K,P,N;
    while(scanf("%lld%lld%lld",&K,&P,&N)!=EOF)
    {
        memset(flag,0,sizeof(flag));
        if(N>P)//坑
        {
            printf("Orz,I can’t find D!\n");
            continue;
        }
        ll tmp=BabyStep_GiantStep(K,N,P);
        if (tmp==-1)
            printf("Orz,I can’t find D!\n");
        else
            printf("%I64d\n",tmp);
    }
    return 0;
}