Problem Description
Fibonacci numbers are well-known as follow: Now given an integer N, please find out whether N can be represented as the sum of several Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. Input
Multiple test cases, the first line is an integer T (T<=10000), indicating the number of test cases. Each test case is a line with an integer N (1<=N<=109). Output
One line per case. If the answer don’t exist, output “-1” (without quotes). Otherwise, your answer should be formatted as “N=f1+f2+…+fn”. N indicates the given number and f1, f2, … , fn indicating the Fibonacci numbers in ascending order. If there are multiple ways, you can output any of them. Example Input
4 5 6 7 100 Example Output
5=5 6=1+5 7=2+5 100=3+8+89
求输入的数是否满足多个斐波那契数相加，如果满足，从小到大输出 二分答案，1e9内的斐波那契数也才50个
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <cstdio> #include <set> #include <math.h> #include <algorithm> #include <queue> #include <iomanip> #include <ctime> #define INF 0x3f3f3f3f #define MAXN 10005 #define Mod 1000000007 using namespace std; long long f[MAXN],cnt; void init() { f[0]=0; f[1]=1; for(cnt=2; f[cnt-1]<=10000000000; ++cnt) f[cnt]=f[cnt-1]+f[cnt-2]; } long long ans[100]; int main() { cnt=0; init(); //cout<<cnt<<endl; int t; scanf("%d",&t); while(t--) { long long n,nn; int p=0; scanf("%lld",&n); nn=n; while(n) { int low=1,high=cnt,mid; while(low<=high) { mid=(low+high)>>1; if(f[mid]==n) { high=mid; break; } else if(f[mid]<n) low=mid+1; else high=mid-1; } n-=f[high]; ans[p++]=f[high]; } printf("%lld=%lld",nn,ans[p-1]); for(int i=p-2;i>=0;--i) printf("+%lld",ans[i]); printf("\n"); } return 0; }