ACM 数论 Interesting Integers

本文主要是介绍ACM 数论 Interesting Integers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Undoubtedly you know of the Fibonacci numbers. Starting with $F_1 = 1$ and $F_2 = 1$ ,every next number is the sum of the two previous ones. This results in the sequence $\cdot\cdot\cdot$ .

Now let us consider more generally sequences that obey the same recursion relation

$=G_{i-1} +G_{i-2}$ for $i > 2$

but start with two numbers $G_1 \le G_2$ of our own choice. We shall call these Gabonacci sequences. For example, if one uses $G_1 = 1$ and $G_2 = 3$ , one gets what are known as the Lucas numbers: $1,3,4,7,11,18,29,\cdot\cdot\cdot$ . These numbers are – apart from $1$ and $3$ – different from the Fibonacci numbers.

By choosing the first two numbers appropriately, you can get any number you like to appear in the Gabonacci sequence. For example, the number n appears in the sequence that starts with $1$ and $n - 1$ , but that is a bit lame. It would be more fun to start with numbers that are as small as possible, would you not agree?

Input Format

On the first line one positive number: the number of test cases, at most $100$ . After that per test case:

one line with a single integer $n$ $\le n \le 10^9)$ : the number to appear in the sequence.

Output Format

Per test case:

one line with two integers $a$ and $b$ $\le b)$ ,such that,for $G_1 = a$ and $G_2 = b, G_k = n$ for some $k$ . These numbers should be the smallest possible, i.e., there should be no numbers $a^{'}$ and $b^{'}$ with the same property, for which ${'} < b$ , or for which ${'} = b$ and ${'} < a$ .

样例输入

样例输出

题意：

类斐波那契数列是改变前两个数生成一个新的数列，问题是给你一个数，让你求出他是以那两个数为首的数列中的数，如果有多组解，求出最小的。

分析：

设前两个数为G(1) G(2),我们不难发现一个规律，G(k)=F(k-2)G(1)+F(k-1)G(2);

那么问题就转化为已知r求满足r=xa+yb的最小一组a,b;

y由于有两个变量要求，我们不妨先设一个变量为自变量，根据自变量求出相应的另一个变量，然后判断是否符合题解；

代码：

#include<stdio.h>
using namespace std;//这里一定要用自己写的数组，不然会超时；
long long f[]={0, 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};
int main()
{
int k,i,j,flag;
long long a,b,n;//ll形式
scanf("%d",&k);
while(k--)
{
a=0;
b=0;
flag=0;
scanf("%lld",&n);
for(b=1;b<=1000000000;b++)//让b从最小的开始，得到的结果自然就是最小的
{
for(j=2;j<=45;j++)//根据for(i=3;(f[i]=f[i-1]+f[i-2])<=1000000000;i++)记录下i即可发现i为46
{
if(f[j]*b>n)
break;
a=(n-f[j]*b)/f[j-1];
if((a>0)&&(a<=b)&&(f[j-1]*a+f[j]*b==n))//此处还要在判断一次是否相等，防止出现前面除法运算是的误差出现
{
flag=1;
break;
}
}
if(flag==1)
break;
}
printf("%lld %lld\n",a,b);
}
return 0;
}