1. 题目

传送门=￣ω￣=

2. 题解

居然比赛的时候想出来正解了。

设广义斐波那契数列：$A$，第 $i$项为 $A_i$

设 “狭义”（一般）斐波那契：$Fib$，第 $i$项为 $Fib_i$

则：$A_i=A_1\times Fib_{i-2}+A_2\times Fib_{i-1}$

那么题目要求：$A_k=m(MOD\ p)$

即：$A_1\times Fib_{k-2}+A_2\times Fib_{k-1}=m(MOD\ p)$

其中 $A_1,k,m,p$均已知，只有 $A_2$未知。

设 $G=A_1\times Fib_{k-2}$

则：$G+A_2\times Fib_{k-1}=m(MOD\ p)$

$A_2\times Fib_{k-1}=m-G(MOD\ p)$

显然这就是个线性同余方程了，求出最小整数解然后求解的个数即可。

其中计算 $Fib_{k-1},Fib_{k-2}$可以 $O(log_2k)$的复杂度求出。

总复杂度 $O(T\times log_2k)$

求斐波那契数列我没用矩阵乘法，用了这个：传送门=￣ω￣=，可以去参考一下～

代码（有点凌乱）：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
LL cur,pre,MOD,T,G,X,Y,t;
void dfs(LL a)
{
    if(a==1){pre=0,cur=1;return;}
    if(a==2){pre=cur=1;return;}
    if(a&1){dfs(a-1),swap(pre,cur),cur=(pre+cur)%MOD;return;}
    dfs(a>>1);
    LL tem=cur;
    cur=(cur*cur%MOD+((cur*pre%MOD)<<1)%MOD)%MOD;
    pre=(tem*tem%MOD+pre*pre%MOD)%MOD;
}
LL exgcd(LL a,LL b,LL&x,LL&y)
{
    if(!b){x=1,y=0;return a;}
    int tmp=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return tmp;
}
int main()
{
    IN(T);
    begin:while(T--)
    {
        LL a,l,r,k,m,F1,F2;
        IN(a),IN(l),IN(r),IN(k),IN(MOD),IN(m);
        if(k==1)
        {
            if(a%MOD==m)puts("1");
            else puts("0");
            goto begin;
        }
        if(k==2)
        {
            printf("%lld\n",((l-1)/MOD)-(r/MOD));
            goto begin;
        }
        a%=MOD,dfs(k-1),F1=pre,F2=cur;
        m=((m-(F1*a)%MOD)%MOD+MOD)%MOD;
        G=exgcd(F2,MOD,X,Y);
        if(m%G){puts("0");goto begin;}
        t=MOD/G,X=((X*m/G)%t+t)%t;
        if(X>r){puts("0");goto begin;}
        r-=X;
        if(X>l)l=0;else l-=X;
        printf("%lld\n",((r+t)/t)-((l+t-1)/t));
    }
    return 0;
}