此篇题解可以通过 \(1\le t\le 2\times10^5,1\le n,k\le10^{18}\) ，不保证 \(\sum n\le2\times 10^5\) 的数据（绝对不是因为没仔细看数据范围）。
题意
\(t\) 组询问，每组给出 \(n\) 和 \(k\)，求有多少个单调不递减且非负的类斐波那契数列满足 \(f_k=n\)。
分析
类斐波那契数列有性质：
其中，\(F\) 表示以 \(F_1=1,F_2=1\) 作为起始的斐波那契数列。它的证明方法可以使用定义 \(f_n=f_{n-1}+f_{n-2}\)，不断把下标大的一项展开成两项之和，具体过程这里就不细说了。
对于这道题，相当于求解方程 \(f_1\times F_{k-2}+f_2\times F_{k-1}=n\)。
题目中 \(1\le k\le10^9\)，似乎无法简单求出 \(F_{k-2}\) 与 \(F_{k-1}\) 的值（假装你不知道矩阵快速幂）。但是观察到，题目要求这个序列非负，所以 \(n\ge F_{k-1}\ge F_{k-2}\)。
可以得出结论，当 \(F_{k-1}>n\) 时，答案为 \(0\)。就算当 \(n=10^{18}\) 时，\(k\) 最大只能取值为 \(88\)。
这样一来，就可以套上扩欧板子解出一组解 \((f_1',f_2')\)。而对于这一类方程，有通解：
易证，\(\gcd(F_{k-1},F_{k-2})=1\)，所以：
由于题目要求，我们还需要满足 \(0\le f_1\le f_2\)。以下默认每算出一个 \(x\)，就按照上式更新一次 \((f_1,f_2)\)。
考虑满足非负性，可以通过取模的方式得到一个使 \(f_2\ge0\) 且 \(f_2\) 最小的解，并相减算出增加的 \(x\) 的值。
然后，如果不满足 \(f_1\le f_2\)，为了使 \(f_2\) 满足上述条件且最小，可以得到 \(x=\lceil\dfrac{f_2-f_1}{F_{k-1}+F_{k-2}}\rceil\)。
观察通解形式，\(f_2\) 随着 \(x\) 的增大而增大，\(f_1\) 随着 \(x\) 的增大而减小，那么若 \(x\ge0\)，总是满足 \(f_1\le f_2\)。所以答案即为 \(\lfloor\dfrac{f_1}{F_{k-1}}\rfloor+1\)。
具体可以对照代码理解。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll N=2e5+10,inf=1e18;
ll T,n,k,f[N];
inline void init(){
f[1]=f[2]=1;
for(int i=3;;++i){
f[i]=f[i-1]+f[i-2];
if(f[i]>inf) break;
}
}
inline ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
init();
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&k);
int px=upper_bound(f+1,f+89,n)-f;
ll x,y;
if(k>px){
puts("0");
continue;
}
ll d=exgcd(f[k-2],f[k-1],x,y);
if(n%d){
puts("0");
continue;
}
x*=n/d,y*=n/d;//解出一组解
ll t=((y%f[k-2]+f[k-2])%f[k-2]-y)/f[k-2];
x-=t*f[k-1],y+=t*f[k-2];//让 f2 非负
if(x>y){//让 f1<=f2
t=(x-y+f[k-1]+f[k-2]-1)/(f[k-1]+f[k-2]);
x-=t*f[k-1],y+=t*f[k-2];
}
if(x<0) {
puts("0");
continue;
}
printf("%lld\n",x/f[k-1]+1);
}
return 0;
}