uva 10225

折騰了我三天之久

首先是BSGS策略

a^x ≡ b (mod m) gcd(a,m)=1

而要決定一個正整數n，思考了很久為何是sqrt(m)

假設使用普通的解法，暴力解x從0代到出現答案為止

出現了已經出現過的數字假設

2^x ≡3 (mod 5)

x=0 (2^x)mod 5=1

x=1 (2^x)mod 5=2

x=2 (2^x)mod 5=4

x=3 (2^x)mod 5=3 答案 但是如果繼續找

x=4 (2^x)mod 5=1 發現重複

x=5 (2^x)mod 5=2 而這個式子也等於(1*2)mod 5也等於一開始的兩種情況

等於是進入迴圈了

所以最高的步數也只要m，在<=m的情況下 一定能找到重複，而進入迴圈

頂多就是0~m-1都有位置剛剛好補滿

 

所以BSGS也使用這個方法，不過也只是用模倒數的方式去算

BS需要時間是暴力的O(n)

GS只需要O(m/n)因為是利用基數排序的想法

所以最快的方式也就是n=sqrt(m)，O(sqrt(m))

傷腦筋的題目......

//============================================================================
// Name        : Discrete Logging.cpp
// Date : 2013/4/19 下午12:20:32
// Author : GCA
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\
    printf("%d ",dp[htx][hty]);}Pln();}
#define M 55
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define Is_debug true
#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
    int tmp=min(x,y);
    return min(tmp,z);
}
int max3(int x,int y,int z){
    int tmp=max(x,y);
    return max(tmp,z);
}
map<Int,Int> mid;
Int p,b,n;
Int x,y;
Int exgcd(Int a,Int b){
    if(!b){
        x=1;y=0;
        return a;
    }
    Int tmp=exgcd(b,a%b);
    Int xx=x;
    x=y;
    y=xx-(a/b)*y;
    return tmp;
}
Int inverse(Int a,Int m){
    exgcd(a,m);
    x=(x+m)%m;
    Int lx=x;
//    debug("%d\n",lx);
    return lx;
}
Int solve(){
    Int sqrtp=sqrt(p);
    Int tmp=1;
    for(Int i=0;i<sqrtp;i++){
        if(tmp==n)return i;
        if(!mid.count(tmp))mid[tmp]=i;
        tmp=(tmp*b)%p;
    }
    Int inv=inverse(tmp,p);
    for(Int i=0;i<sqrtp+1;i++){
        if(mid.count(n))return i*sqrtp+mid[n];
        n=(n*inv)%p;
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(0);

    while(~scanf("%lld%lld%lld",&p,&b,&n)){
        Int ans=solve();
        if(ans!=-1){
            printf("%lld\n",ans);
        }else{
            printf("no solution\n");
        }
        mid.clear();
    }

}