Poj 2417ステップアルゴリズム

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

#define INF 1000000007
#define mo 1000007
typedef long long ll;
struct node{
    ll m,data;
    int next;
}hash[1000000];
ll t,m,k,p,a,b,x,y,first[mo+1],tot,ans; 

void insert(ll x,ll m){
    int y=x%mo;
    hash[++tot].data=x;
    hash[tot].next=first[y];
    hash[tot].m=m;
    first[y]=tot;
}

void find(ll x,ll k){
    ll y=x%mo;
    for(int i=first[y];i;i=hash[i].next){
        if(hash[i].data==x&&k*t-hash[i].m>=0)
        ans=min(ans,k*t-hash[i].m);
    }
}

ll power(ll a,ll b,ll p){
    ll tmp=1;
    while(b){
        if(b&1)tmp=tmp*a%p;
        a=a*a%p; b/=2;
    }
    return tmp;
}

int main(){
    while(~scanf("%lld%lld%lld",&p,&a,&b)){
        memset(first,0,sizeof(first));
        t=(ll)sqrt(p)+1;
        x=1; b=power(b,p-2,p);
        for(int i=0;i<=t;i++){
            insert(x,i);
            x=x*a%p;
        }
        ans=INF;
        x=power(a,t,p); y=1;
        for(k=0;k<=t;k++){
            find(y*b%p,k);
            y=y*x%p;
        }
        if(ans==INF)puts("no solution");
        else printf("%lld
",ans);
    }
    return 0;
}