求A^x=B(%C)

x = i * m + j ( 0 <= i < m, 0 <=j < m) m = Ceil ( sqrt(C) );

hash[i]====A^i%C

然后枚举i，使得AA=(A^M)^i

即初始的公式变成AA*A^j=B(%C)

若A^j为x，则就变成AA*X=B(%C)，然后我们可以用扩展欧几里德来算出x。

然后对于X，去hash表里查询是否存在。

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define LL long long
#define lcm(a,b) (a*b/gcd(a,b))
//O（n）求素数，1-n的欧拉数
#define N 1500001
struct math_use
{
    LL run_exgcd(LL a,LL b,LL &x,LL &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        LL _r=run_exgcd(b,a%b,x,y);
        LL t=x;
        x=y;
        y=t-a/b*y;
        return _r;
    }
    LL exgcd(LL a,LL b,LL c,LL &x,LL &y)
    {
        LL p=run_exgcd(a,b,x,y);
        if(c%p)return -1;
        x=(x*c/p)%b;
        LL t=b/p;
        x=(x%t+t)%t;
        return p;
    }
    LL q_mod(LL a,LL b,LL n)
    {
        LL ret=1;
        LL tmp=a;
        while(b)
        {
            //基数存在
            if(b&0x1) ret=ret*tmp%n;
            tmp=tmp*tmp%n;
            b>>=1;
        }
        return ret;
    }
}M;


struct hash_use
{
    LL x;
    int ip;
    friend bool operator <(const hash_use &a,const hash_use &b)
    {
        if(a.x!=b.x)return a.x<b.x;
        else return a.ip<b.ip;
    }
}hash[110000];
int select(LL x,int m)
{
    int l=0;
    int r=m+1;
    int mid=(l+r)/2;
    while(l<r)
    {
        if(hash[mid].x>=x)r=mid;
        else l=mid+1;
        mid=(l+r)/2;
    }
    if(hash[mid].x!=x)return -1;
    return hash[mid].ip;
}
LL dos(LL a,LL b,LL c)
{
    LL m=ceil(sqrt(c));
    memset(hash,0,sizeof(hash));
    for(int i=0;i<=m;i++)
    {
        hash[i].x=M.q_mod(a,i,c);
        hash[i].ip=i;
    }
    sort(hash,hash+m+1);
    LL s=M.q_mod(a,m,c);
    for(int i=0;i<=m;i++)
    {
        LL aa=M.q_mod(s,i,c);
        LL x,y;
        M.exgcd(aa,c,b,x,y);
        int sel=select(x,m);
        if(sel!=-1)
        {
            return i*m+sel;
        }
    }
    return -1;
}
int main()
{
    LL p,g,y;
    while(cin>>p>>g>>y)
    {
        LL ans=dos(g,y,p);
        if(ans==-1)cout<<"ERROR"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}