自动搬运

查看原文

来自洛谷，原作者为

	Nightsky_Stars .

搬运于2025-08-24 22:54:37，当前版本为作者最后更新于2024-01-24 09:59:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为在 $10^{18}$ 的范围的斐波那契数只有 $86$ 项，所以考虑暴搜。

看每一个斐波那契数能否整除 $n$，能就除掉接着找，不能就从比他小的下一个开始。

如果 $n = 1$，就不能再除了，以及如果除数为 $1$ 时，也不能继续。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[105]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931};//预处理斐波那契数
ll dfs(ll n,ll x){
	if(n==1){
		return 1;
	}
	if(x==1){
		return 0;
	}//处理边界
	while(n<f[x]){
		x--;
	}
	ll ans=0;
	if(!(n%f[x])){
		ans+=dfs(n/f[x],x);//选这个数
	}
	return ans+dfs(n,x-1);//不选这个数，进入下一层
}
int main(){
	ll t,n;
	cin>>t;
	while(t--){
		cin>>n;
		cout<<dfs(n,86)<<"\n";
	}
	return 0;
}