POJ 2417

towboa / 2023-07-02 / 原文

求解　a^x≡b (mod c)

( x<c )

siz = sqrt( c )

a^( i*siz + j) ≡b (mod c)

a^j ≡ a^( - i* siz) *b (mod c)

枚举 j , 将 (j, a^j %c ) 存入map ;

枚举 i, 查询map的值 ( a^(-i *siz) *b %c

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 1e18
 void gcd(int a,int b,int &d,int &x,int &y){
 	if(b==0){
 		 d=a; x=1,y=0; return ;
	 }
	gcd(b,a%b,d,y,x); y-=x*(a/b);
 }
 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];
    }
}mp ;

int BSGS(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;
    }
 
    mp.clear();
    int Size=ceil(sqrt(C)),D=1,Base=1;
    for(int i=0;i<=Size-1;i++){//将A^j存进哈希表
        mp[Base]=min(mp[Base],i);//存储最小的
        Base=(Base*A)%C;
    }
    for(int i=0;i<=Size-1;i++){//扩展欧几里得求A^j
        int x,y;
        int g; gcd(D,C,g,x,y);
        x=(x*B%C+C)%C;
        if(mp.count(x))
            return i*Size+mp[x];
        D=(D*Base)%C;
    }
    return -1;
}
 
 signed main(){
     int A,B,C;
    while(cin>>C>>A>>B){
        int res=BSGS(A,B,C);
        if(res==-1)
            printf("no solution\n");
        else
            printf("%lld\n",res);
    }
 }