【SPOJ】Power Modulo Inverted（拓展BSGS）

题面

洛谷

求最小的\(y\)
满足
\[k\equiv x^y(mod\ z)
\]
题解

拓展\(BSGS\)模板题
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

const int HashMod=123456;

struct HashTable

{

	struct Line{int u,v,next;}e[100000];

	int h[HashMod],cnt;

	void Add(int u,int v,int w){e[++cnt]=(Line){w,v,h[u]};h[u]=cnt;}

	void clear(){memset(h,0,sizeof(h));cnt=0;}

	void Insert(int x,int i)

	{

		int k=x%HashMod;

		Add(k,i,x);

	}

	int Query(int x)

	{

		for(int i=h[x%HashMod];i;i=e[i].next)

			if(e[i].u==x)return e[i].v;

		return -1;

	}

}Hash;

int fpow(int a,int b,int MOD)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

void NoAnswer(){puts("No Solution");}

void ex_BSGS(int y,int z,int p)

{

	if(z==1){puts("0");return;}

	int k=0,a=1;

	while(233)

	{

		int d=__gcd(y,p);if(d==1)break;

		if(z%d){NoAnswer();return;}

		z/=d;p/=d;++k;a=1ll*a*y/d%p;

		if(z==a){printf("%d\n",k);return;}

	}

	Hash.clear();

	int m=sqrt(p)+1;

	for(int i=0,t=z;i<m;++i,t=1ll*t*y%p)Hash.Insert(t,i);

	for(int i=1,tt=fpow(y,m,p),t=1ll*a*tt%p;i<=m;++i,t=1ll*t*tt%p)

	{

		int B=Hash.Query(t);if(B==-1)continue;

		printf("%d\n",i*m-B+k);return;

	}

	NoAnswer();

}

int main()

{

	int x,z,k;

	while(233)

	{

		x=read();z=read();k=read();

		if(x==0&&z==0&&k==0)break;

		ex_BSGS(x,k,z);

	}

	return 0;

}