BZOJ 3239 Discrete Logging BSGS

タイトル:リンク
方法:BSGS
解析:
おじいさんはBSGSを話し終わって、とても辛いorzです.
これらの数論は死ぬほど生きなければならない.
これは裸BSGSの問題です.
方程式A^x=B(mod C)の最小の非負の整数xを求めます.
暴枚はすべて通過できないので、次は複数のデータなのでどう思いますか.
私たちは全体の問題を半分に分けて、前半について、私たちは値を先に計算してハッシュ表に投げて、それから後半に答えをまとめることができる値がハッシュ表の中にあるかどうかを探して、ハッシュ表の中で、最初に探されたのはきっと最小です.
このアルゴリズムはよくわかりますが、Cは素数なら分析でも書きます.
コード:

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 140345
using namespace std;
typedef long long ll;
int head[mod+10];
ll c,a,b,ans;
int cnt;
struct node
{
    int from,to,next;
    ll val;
}edge[mod+10];
ll get_inv(ll x,ll y)
{
    ll ret=1;
    while(y)
    {
        if(y&1)ret=(ret*x)%c;
        x=(x*x)%c;
        y>>=1;
    }
    return ret;
}
void init()
{
    memset(head,-1,sizeof(head));
    cnt=1;
}
void edgeadd(int from,int to,ll val)
{
    edge[cnt].from=from,edge[cnt].to=to,edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void BSGS(int A,int B,int C)
{
    //A^x=B(mod C);
    int m=(int)ceil(sqrt(C));
    ll k=1;
    edgeadd(1,0,1);
    for(int i=1;i<m;i++)
    {
        k=(k*A)%C;
        int flag=0;
        for(int j=head[k%mod];j!=-1;j=edge[j].next)
        {
            int val=edge[j].val;
            if(val==k){flag=1;break;}
        }
        if(!flag)edgeadd(k%mod,i,k);
    }
    k=(k*A)%C;
    ll D=1;
    ll inv=get_inv(D,C-2);
    ll tmp=B*inv%C;
    ans=-1;
    for(int j=head[tmp%mod];j!=-1;j=edge[j].next)
    {
        int val=edge[j].val;
        if(val==tmp)
        {
            ans=edge[j].to;break;
        }
    }
    if(ans!=-1){printf("%lld
",ans);return;}
    for(int i=1;i<=m;i++)
    {
        D=D*k%C;
        inv=get_inv(D,C-2);
        tmp=B*inv%C;
        for(int j=head[tmp%mod];j!=-1;j=edge[j].next)
        {
            int val=edge[j].val;
            if(val==tmp)
            {
                ans=edge[j].to+i*m;
                break;
            }
        }
        if(ans!=-1){printf("%lld
",ans);return;}
    }
}
int main()
{
    while(~scanf("%lld%lld%lld",&c,&a,&b))
    {
        init();
        BSGS(a,b,c);
        if(ans==-1)puts("no solution");
    }
}