【数学规律】Sleepy Kaguya

链接:https://ac.nowcoder.com/acm/contest/338/C
来源:牛客网

Houraisan☆Kaguya is the princess who lives in Literally House of Eternity. However, she is very playful and often stays up late. This morning, her tutor, Eirin Yagokoro was going to teach her some knowledge about the Fibonacci sequence. Unfortunately, the poor princess was so sleepy in class that she fell asleep. Angry Eirin asked her to complete the following task:

This sequence can be described by following equations:
    1.F[1]=F[2]=1

    2.F[n]=F[n-1]+F[n-2]  (n>2)

Now, Kaguya is required to calculate F[k+1]*F[k+1]-F[k]*F[k+2] for each integer k that does not exceed 10^18.

Kaguya is so pathetic. You have an obligation to help her.
(I love Houraisan Kaguya forever!!!)
image from pixiv,id=51208622

输入描述:

Input
Only one integer k.

输出描述:

Output
Only one integer as the result which is equal to F[k+1]*F[k+1]-F[k]*F[k+2].
示例1

输入

复制

2

输出

复制

1

说明

F[2]=1,F[3]=2,F[4]=3

2*2-1*3=1

备注:

0 < k ≤ 1^18

If necessary, please use %I64d instead of %lld when you use "scanf", or just use "cin" to get the cases.

分析:

题的公式是斐波那契公式 F[1]=F[2]=1,F[n]=F[n-1]+F[n-2]
输入一个数k代表第k个斐波那契数,输出 F[k+1]*F[k+1]-F[k]*F[k+2]的结果。
1e18的复杂度肯定暴力常规做法不行。
打了个表发现,只有1和-1两种情况,考虑和前一项的关系。
发现后一项是前一项的相反数。

证明:

G(k)=F[k+1]*F[k+1]-F[k]*F[k+2]
=F[k+1]*F[k+1]-F[k]*(F[k]+F[k+1])
=(F[k+1]-F[k])*F[k+1]-F[k]*F[k]
=F[k-1]*F[k+1]-F[k]*F[k]
所以G(k)=-G(k-1)

根据样例,当k=2时,值为1。可知奇数时为-1,偶数为1.

代码:

#include <iostream>
using namespace std;
int main()
{
  long long k=0;
  cin >> k;
  if (k & 1)
    cout << "-1" << endl;
  else
    cout << "1" << endl;
  return 0;
}

 

发表评论

电子邮件地址不会被公开。