根据鸽笼原理，在p次后一定循环，一眼BSGS。
发现他给的函数是个一次函数，一次函数有什么性质呢？f(f(x))还是一次函数，这样就能做了。
首先我们暴力预处理出f(f(f(x)))......sqrt(p)层的f(x)。
然后预处理出前sqrt(p)迭代后的值。
我们可以用exgcd求出如果让f(x)=t，我们需要的x值。
然后我们枚举用多少层迭代sqrt(p)后的f(x)即可。
注意特判一下a==0的情况，因为exgcd无法处理有0的参数。
为什么跑得如此之慢?可能我需要一个unordered_map，然而C++11不能用......
代码:
#include<cstdio>
#include<cmath>
#include<map>
typedef long long int lli;
using namespace std; lli mod; struct Poly {
lli k,b;
inline Poly inter(const Poly &t) {
return (Poly){t.k*k%mod,(t.b*k%mod+b)%mod};
}
inline lli ite(const lli &x) {
return ( k * x % mod + b ) % mod;
}
}now,trans,sqr; inline lli exgcd(lli a,lli b,lli &x,lli &y) {
if( !b ) {
x = , y = ;
return a;
}
lli ret = exgcd(b,a%b,y,x);
y -= ( a / b ) * x;
return ret;
} inline lli getx(const Poly &p,const lli &t) {
lli x,y,rit;
exgcd(p.k,mod,x,y);
rit = ( t - p.b + mod ) % mod , x = ( x % mod + mod ) % mod;
return x * rit % mod;
} inline lli bsgs(lli a,lli b,lli x,lli t) {
if( !a && !b ) return x == t ? : -;
map<lli,lli> mp;
int sq = ( (double) sqrt(mod) + 0.5 ) + ;
sqr = now = (Poly){,} , trans = (Poly){a,b};
for(int i=;i<=sq;i++) {
if( mp.find(x) == mp.end() ) mp[x] = i;
x = trans.ite(x);
}
for(int i=;i<=sq;i++) sqr = trans.inter(sqr);
for(int i=;i<=sq;i++) {
lli tx = getx(now,t);
if( mp.find(tx) != mp.end() ) return mp[tx] + i * sq;
now = sqr.inter(now);
}
return -;
} int main() {
static int T;
static lli a,b,x,t;
scanf("%d",&T);
while(T--) {
scanf("%lld%lld%lld%lld%lld",&mod,&a,&b,&x,&t);
printf("%lld\n",bsgs(a,b,x,t));
}
return ;
}