poj3243 Clever Y[扩展BSGS]

Clever Y

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 8666		Accepted: 2155

Description

Little Y finds there is a very interesting formula in mathematics:

X^Y mod Z = K

Given X, Y, Z, we all know how to figure out K fast. However, given X, Z, K, could you figure out Y fast?

Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers X, Z, K (0 ≤ X, Z, K ≤ 10⁹). 
Input file ends with 3 zeros separated by spaces. 

Output

For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasible Y (0 ≤ Y < Z). Otherwise output the minimum Y you find.

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution

Source

POJ Monthly--2007.07.08, Guo, Huayang

//消除因子，在做普通的BSGS
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
struct Thash{
    static const ll N=1e6+,MOD=;
    ll tot,val[N],h[N],next[N],head[MOD+];
    void clear(){tot=;memset(head,,sizeof head);}
    void insert(ll H,ll VAL){
        for(ll i=head[H%MOD];i;i=next[i]) if(h[i]==H){val[i]=VAL;return ;}
        h[++tot]=H;val[tot]=VAL;next[tot]=head[H%MOD];head[H%MOD]=tot;
    }
    ll get(ll H){
        for(ll i=head[H%MOD];i;i=next[i]) if(h[i]==H) return val[i];
        return -;
    }
}M;
ll gcd(ll a,ll b){
    if(!b) return a;
    return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=;y=;return ;}
    exgcd(b,a%b,d,y,x);
    y-=a/b*x;
}
ll inv(ll a,ll p){
    ll d,x,y;
    exgcd(a,p,d,x,y);
    return d==?(x%p+p)%p:-;
}
ll BSGS(ll a,ll b,ll mod){
    M.clear();
    ll m=(ll)ceil(sqrt(mod+0.5));
    ll t=;
    for(ll i=;i<m;i++){
        M.insert(t,i);
        t=t*a%mod;
    }
    ll base=inv(t,mod);
    ll res=b;
    for(ll i=,z;i<m;i++){
        if((z=M.get(res))!=-) return i*m+z;
        res=res*base%mod;
    }
    return -;
}
ll solve(ll a,ll b,ll mod){
    ll A=,D=,cnt=,ans;
    for(int i=;i<=;i++){
        if(A==b) return i;
        A=A*a%mod;
    }
    for(ll t;(t=gcd(a,mod))!=;){
        if(b%t)return -;
        b/=t;
        mod/=t;
        D*=a/t;D%=mod;
        cnt++;
    }
    b=b*inv(D,mod)%mod;
    ans=BSGS(a,b,mod);
    if(~ans) return ans+cnt;
    return -;
}
int main(){
    ll a,b,c,ans;
    while(~scanf("%lld%lld%lld",&c,&a,&b)){
        ans=solve(a,b%c,c);
        if(~ans) printf("%lld\n",ans);
        else puts("no solution");
    }
    return ;
}