问题描述

There is an infinite integer sequence $f_1,f_2,f_3,...,$ where $f_1=1,f_2=2,f_i=f_{i-1}+f_{i-2}(i >= 3)$ .

You are given two positive integers $n$ and $k$ , your task is to check whether $n$ can be split into $k$ integers $a_1,a_2,...,a_k$ , where $a_1,a_2,...,a_k∈f$ and $a_1+a_2+...+a_k=n$ . Note that you can split $n$ into same integers, for example, $10=5+5=f_4+f_4$ .

输入

The first line of the input contains an integer T(1 <= T <= 100000), denoting the number of test cases.

In each test case, there is one integer $n(1 <= n,k <= 10^{18})$ in the first line.

输出

For each test case, print a single line. If it is possible to split n into $k$ integers, print Yes, otherwise print No.

样例输入

样例输出

No
Yes
Yes
No

解题思路

在做这道题之前，首先得了解一个东西。

任何一个正整数一定能分解成若干个不重复且不相邻的斐波那契数之和

这个就是Zeckendorf理论，详见《任何一个自然数能被不相同的斐波那契数之和表示 - 知乎》。

有了这个理论基础，那么这个问题用贪心算法就会变得特别容易。

思路就是：每次找离数字 $n$ 最近的斐波那契数，然后n -= 这个斐波那契数。

由于斐波那契数列增长得特别快，所以，我们可以直接打表。

long long a[] = {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,
1779979416004714189,2880067194370816120,4660046610375530309,
7540113804746346429};

打表挺容易的，本文不叙述。

那么我们的任务便是在这个数组中寻找离 $n$ 最近的一个数字。

寻找的过程，我们可以用c++stl的函数upper_bound，从而来找一个比 $n$ 大的数字，然后 $- 1$ 来获得一个 $<= n$ 的数字。

while (k --)
{
    v = *(upper_bound(a, a + 91, n) - 1);
    n -= v;
    if (n == 0) break;
}

上述代码就是在数组里寻找，找到一个 $<=n$ 的数字 $v$ 之后， $n$ 减去他，之后继续找一直到n = 0为止。

那么这个时候如果 $k$ 还没用完呢？题目要求是分解成 $k$ 个数字。

没关系，因为每个在斐波那契数列中的数字都能分解成另外2个数字，而且题目说还可以重复，那不就更容易了吗。

但是呢，得注意一把，如果 $k$ 太大，都比 $n$ 都要大了，那肯定不行啊，最小的斐波那契数也就只有1，所以说，判断一下即可。

if (k > n) {
    printf("No\n");
    continue;
}

好了，唯一要注意的就是得开long long。

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return

int main()
{
    ll a[] = {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,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429};
    int T;
    scanf("%d",&T);
    ll n,k;
    ll v;
    while (T --)
    {
        scanf("%lld %lld",&n,&k);
        if (k > n) {
            printf("No\n");
            continue;
        }
        while (k --)
        {
            v = *(upper_bound(a, a + 91, n) - 1);
            n -= v;
            if (n == 0) break;
        }
        if (n == 0) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Split the Number - 第四届全国中医药院校大学生程序设计竞赛