Problem

Description

小W喜欢读书，尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书，这本书一共有$P$页，页码范围为$0 \cdots P-1$。

小W很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用NOI2012上学习的线性同余法生成一个序列，来决定每天具体读哪一页。

我们用Xi来表示通过这种方法生成出来的第$i$个数，也即小W第$i$天会读哪一页。这个方法需要设置$3$个参数$a,b,X1$，满足$0\leq a,b,X1\leq p-1$，且$a,b,X1$都是整数。按照下面的公式生成出来一系列的整数：$X_{i+1} \equiv aX_i+b \pmod p$。

但是这种方法可能导致某两天读的页码一样。

小W要读这本书的第$t$页，所以他想知道最早在哪一天能读到第t页，或者指出他永远不会读到第$t$页。

Input

输入含有多组数据，第一行一个正整数$T$，表示这个测试点内的数据组数。

接下来T行，每行有五个整数$p，a，b，X1，t$，表示一组数据。保证$X1$和$t$都是合法的页码。 注意：$P$一定为质数。

Output

共$T$行，每行一个整数表示他最早读到第$t$页是哪一天。如果他永远不会读到第$t$页，输出-1。

Sample Input

3
7  1 1 3 3
7  2 2 2 0
7  2 2 2 1

Sample Output

1 
3 
-1

HINT

$2 \leq p \leq 10^9$

Solution

Analysis

这其实是个非常简单的题，之所以记录一下题解是因为网上绝大部分的题解都是错的（至少我后来搜到的没有一个是正确的），关于一些特判讲的很含糊。

我们设解为$n$

分类讨论：

  • $a=0$ ：显然只要特判$t=b$就结束了；
  • $a=1$ ：直接解$t \equiv X+(n-1)b$，注意要通过特判$b=0$和$t-x \equiv gcd(p,b)$；
  • $a=others$

首先惯例大力推式子，根据简单的高中数列知识可以推到这样的式子：

很多文章就直接左边式子$X-\frac{b}{1-a}$直接除到了右边，这是显然不对的，因为这个式子可能为$0$。这个就导致了很多题解说要特判$t=x$的情况（但大多数题解都只认为这个只是加速了运算，跟正确性无关），所以我简单解释一下这个特判的重要性。

我们简单回想一下，这个式子为$0$的必要条件应该是$X\equiv \frac{b}{1-a}$。此时如果该方程有解时$t-\frac{b}{1-a} \equiv 0$，也就是说$X=t$。所以说这种特判影响了正确性。同时也解决了case #1 #2中的对于解为$1$的特殊情况。

Attention

其他还有点小细节如在case #2 中的$n+1$不需要取模之类的。

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
il ll ksm(ll x,ll y,ll mod){
    ll res=1;x%=mod;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
il ll inv(ll x,ll mod){
    return ksm(x,mod-2,mod);
}
map<ll,ll> s;
il ll bsgs(ll a,ll b,ll p){
    s.clear();
    ll m=ceil(sqrt(p)),now=b;
    rep(i,0,m){
        s[now]=i;
        now=now*a%p;
    }
    a=ksm(a,m,p);
    now=a;
    rep(i,1,m){
        if(s.find(now)!=s.end())
            return 1ll*i*m-s[now];
        now=now*a%p;
    }
    return -2;
}
il int gcd(int a,int b){
    while(b){
        int t=a;
        a=b;
        b=t%b;
    }
    return a;
}
il void solve(){
    ll p=read(),a=read(),b=read(),x=read(),t=read(),ans=0;
    if(x==t) puts("1");
    else if(a==0){
        if(b==t) puts("2");
        else puts("-1");
    }else if(a==1){
         t=(t-x+p)%p;
        if(b==0 || t%gcd(b,p)) puts("-1");
        else{
            ans=(t*inv(b,p)%p+1;
            printf("%lld\n",ans);
        }
    }else{
        ll res=b*inv((1-a+p)%p,p)%p;
        res=(t-res+p)%p*inv((x-res+p)%p,p)%p;
        ans=bsgs(a,res,p)+1;
        printf("%lld\n",ans);
    }
}
int main(){
    int T=read();
    while(T--) solve();
    return 0;
}

一个好奇的人