1853B - Fibonaccharsis - CodeForces Solution

#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
ll countSol(ll coeff[], ll n, ll rhs)
{
    // Create and initialize a table
    // to store results of subproblems
    ll dp[rhs + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
 
    // Fill table in bottom up manner
    for (ll i = 0; i < n; i++)
    for (ll j = coeff[i]; j <= rhs; j++)
        dp[j] += dp[j - coeff[i]];
 
    return dp[rhs];
}
ll solFinder(ll n,ll x,ll y){
	ll ans=0;
	for(ll i=0;i<=200015;i++){
		if(n-x*i>=0){
			ll r1=n-x*i;
			ll r2=(n-x*i)%y;
			ll r3=(n-x*i)/y;
			if(r2==0 and i<=r3){
				ans++;
			}
		}
		else break;
	}
	return ans;
}
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--){
		ll n,k;cin>>n>>k;
		ll z=200000;
		bool flag=true;
		if(k>z){
			cout<<0<<endl;
			continue;
		}
		vector<ll> x,y;
		x.pb(1);
		x.pb(0);
		x.pb(1);
		y.pb(0);
		y.pb(1);
		y.pb(1);
		for(int i=3;i<k;i++){
			x.pb(y[i-1]);
			y.pb(y[i-1]+x[i-1]);
			//cout<<x[i]<<" "<<y[i]<<endl;
			if(x[i]>z or y[i]>z){
				cout<<0<<endl;
				flag=false;
		    	break;
			}
		}
		
		if(flag){
			ll x1=x[k-1];
			ll y1=y[k-1];
			cout<<solFinder(n,x1,y1)<<endl;
		}
		
	}
}