```cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void Swap(int&x,int&y){x^=y;y^=x;x^=y;}
typedef long long ll;
map<ll,ll>hash;
ll p,b,n;
inline ll qpow(ll a,ll b,ll MOD)
{
ll ans(1ll);
while(b)
{
if(b&1) ans=ans*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld",&p,&b,&n);
if(b%p==0&&n%p!=0)
{
puts("no solution");
return 0;
}
ll g=ceil(sqrt(p));
for(register ll i=0,h=n%p;i<g;i++,h=h*b%p) hash[h]=i;
ll base,now;
base=now=qpow(b,g,p);
for(register ll i=1;i<=g;i++)
{
if(hash[now])
{
printf("%lld\n",((i*g-hash[now])%p+p)%p);
return 0;
}
now=now*base%p;
}
puts("no solution");
return 0;
}
```
by UperFicial @ 2021-07-17 17:21:37
@[zimujunqwq](/user/118196) 不用取最小值吧,因为我的 $i$ 是从小到大枚举的啊/yiw
求问哪里取模要膜 $p-1$ 啊/xk
by UperFicial @ 2021-07-17 17:43:15
@[zimujunqwq](/user/118196) 嘛,现在没事儿了,菜鸡 A 了/xk
by UperFicial @ 2021-07-17 17:45:41
@[zimujunqwq](/user/118196) 噢噢噢噢对哦,谢谢神仙orz/cy
by UperFicial @ 2021-07-17 17:49:32
@[UperFicial](/user/360511) 其实既然如果 $x = tm + r, t, r \in[1, m]$ 的话应该正好保证了 $x$ 一一对应 $[0, p - 1]$ 中的整数,所以根本不用取模(
那我刚才说的模 $p - 1$ 估计错了我爬
by zimujun @ 2021-07-17 17:52:05
对不起,浪费您时间了,刚才说的可能全部无效
by zimujun @ 2021-07-17 17:52:57
@[UperFicial](/user/360511)
真正的问题是:
```cpp
if(hash[now])
```
如果哈希表里存的是 $0$ 的话就会错过,应该写作
```cpp
if(hash.count(now))
```
by zimujun @ 2021-07-17 17:57:58
@[zimujunqwq](/user/118196) 没事儿的啦/cy
非常感谢神仙/qq
by UperFicial @ 2021-07-17 18:02:46
根本不是块长取小或者模数的问题(
至于块长取大为什么能对,可能是因为哈希表中的值为 $0$ 的可能性极小,而恰恰样例正好踩到了存到 $0$ 的地方,取大块长又把样例避开了
模数则不是本质的问题,答案不可能是 $p - 1$ 因为如果 $p - 1$ 可以 $0$ 一定可以
by zimujun @ 2021-07-17 18:03:43
我将您那份不过样例的代码交了上去,然后 [AC](https://www.luogu.com.cn/record/53415788) 了,实证哈希表内存到 $0$ 的可能性确实很小(
《关于样例比所有测试数据都强这档事》
by zimujun @ 2021-07-17 18:06:14