Description：

给定 $p,a,b,x_1$ ，现有一数列： $$ x_{i+1}=(x_i\times a+b)\mod p $$ ​

求最小的 $i$ 满足 $x_i=t$ 。

$0\leqslant a<P,0\leqslant b<P,2\leqslant P\leqslant 10^9$

Solution：

$$ \begin{align} x_i&=(x_{i-1}\times a+b)\\ &=a^{i-1}\times x_1+a^{i-2}b+a^{i-3}b+\cdots+b\\ &=a^{i-1}\times x_1+b\times \frac{a^{i-1}-1}{a-1} \end{align} $$

得到： $$ a^{i-1}=\frac{x_i+b(a-1)^{-1}}{x_1+b(a-1)^{-1}} $$ 注意各种特判。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll BSGS(ll p,ll a,ll b)

{

	if(b == 1)return 1;

	map<ll,ll> s;

	ll w = sqrt(p);

	ll i,cur;

	for(i = 0,cur = 1;i < w;++i,cur = cur * a % p)

	{

		s[cur * b % p] = i;

	}

	ll power = cur;

	for(i = 1;i <= w + 1;++i,power = power * cur % p)

	{

		if(s.find(power) != s.end())return i * w - s[power] + 1;

	}

	return -1;

}

ll power(ll a,ll b,ll p)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % p;

		a = a * a % p;

		b = b >> 1;

	}

	return res;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	ll p,a,b,x1,t;

	while(testcases--)

	{

		scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);

		if(x1 == t){puts("1");continue;}

		if(a == 1)

		{

			if(b == 0){puts("-1");continue;}

			else

			{

				ll ans = ((t - x1 + p) % p * power(b,p - 2,p) % p + 1) % p;

				if(ans == 0)ans += p;

				printf("%lld\n",ans);

				continue;

			}

		}

		if(a == 0)

		{

			if(b == t){puts("2");continue;}

			else{puts("-1");continue;}

		}

		ll inv = power((a - 1 + p) % p,p - 2,p);

		ll P = p,A = a % p,B = (t + b * inv % p) % p * power((x1 + b * inv % p) % p,p - 2,p) % p;

		printf("%lld\n",BSGS(P,A,B));

	}

	return 0;

}