BAPC2014 I&&HUNNU11589:Interesting Integers
题意:
对于我们已知的斐波那契数列,现在给出一个n,要我们求出一个新的斐波那契数列起始项,使得n能在新的斐波那契数列中,要求起始项y最小
思路:
我们知道
a3 = a1+a2
a4 = a1+2*a2
a5 = 2*a1+3*a2
a6 = 3*a1+5*a2
可以得到
an = fib[n-2]*a[1]+fib[n-1]*a[2]
然后我们只需要枚举就可以了,猜测a[2]不会超过10W,然后居然也过了
队友用数学方法解的,那个才是正解,暴力是邪门歪道,囧
http://blog.csdn.net/u010579068/article/details/47452185
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define ULL unsigned long long
#define N 100005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 1000000007;
LL fib[50]= {0,0,1};
LL n ;
int main()
{
LL i,j,k;
for(i = 3; i<50; i++)
{
fib[i] = fib[i-1]+fib[i-2];
}
int t;
scanf("%d",&t);
while(t--)
{
scanf("%I64d",&n);
int flag = 0;
LL x,y,tz,ty;
for(i = 45; i>2; i--)
{
for(ty=1; ty<=100000; ty++)
{
int tem = n-ty*fib[i];
if(ty*fib[i]+fib[i-1]>n)
break;
else if(tem%fib[i-1]==0&&tem/fib[i-1]<=ty)
{
x = tem/fib[i-1];
y = ty;
flag = 1;
break;
}
}
if(flag)
break;
}
printf("%I64d %I64d\n",x,y);
}
return 0;
}
版权声明:本文为libin56842原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。