[BZOJ 3239][poj 2417]Discrete Logging(BSGSアルゴリズム)

タイトルの説明
トランスファゲート
問題解
BSGSアルゴリズム.ここでPは素数であるので、BがPを除去できるか否かを判断するだけでよい.mapの使い方に注意してください.
コード#コード#

#include
#include
#include
#include
#include
using namespace std;
#define LL long long

map  hash;
LL P,B,N,m,B_m,mul,now,ans;
bool pd;

inline void clear(){
    pd=false;
    hash.clear();
}

inline LL fast_pow(LL a,LL p){
    LL ans=1;
    for (;p;p>>=1,a=(LL)(a*a)%P)
      if (p&1)
        ans=ans*a%P;
    return ans;
}

int main(){
    while (~scanf("%lld%lld%lld",&P,&B,&N)){
        if (B%P==0){
            printf("no solution
");
            continue;
        }

        clear();

        m=ceil(sqrt(P));
        B_m=fast_pow(B,m);

        mul=1;
        now=mul*N%P;
        hash[now]=0;
        for (int j=1;j<=m;++j){
            mul=mul*B%P;
            now=mul*N%P;
            hash[now]=j;
        }

        mul=1;
        for (int i=1;i<=m;++i){
            mul=mul*B_m%P;
            if (hash[mul]){
                pd=true;
                ans=i*m-hash[mul];
                printf("%lld
",ans);
                break;
            }
        }

        if (!pd) printf("no solution
");
    }
}

まとめ
①わからないことがあったら、口を開けずに人に聞いて、自分で考えてもわからないまま聞いてみる(大事!!)②ここでのマッピング配列はhashテーブルを格納する方法に注意し,空間不足を解決できる.③爆intの場合、最近よくある問題です.