K - Kernel Of Love

K - Kernel Of Love 

Mr. Potato Head works on Unified Non-linear Algorithms about Love (UNAL). These algorithms are connected to a traditional machine learning branch called Kernel methods. Mr. Potato Head has discovered a Kernel function which measures the similarity of two persons and hence can predict the likelihood of them being a good couple. He has taken his discoveries one step forward, after running a Kernel algorithm over a vast database of Facebook profiles, he made some interesting (albeit scary) discoveries: every single human can be mapped bijectively to a Fibonacci number, which allowed him to derive a formula that tells if a couple will be happy for ever and ever.

The Fibonacci numbers are the sequence of numbers {F_k}∞k=1 defined by the linear recurrence equation

with F₁=F₂=1

A perfect couple is represented by two numbers x and y such that:

1. xx and yy are Fibonacci numbers.
2. They are attractive to each other but not too much, this holds true when gcd(x,y)=1
   
3. They are not too different or too similar, this is achieved when (x+y)mod2=1
   
4. Their eternal combination leads to another human being, this means, another Fibonacci number. This happens when x+y=z where z is a Fibonacci number.

Mr. Potato Head is astonished with his discovery, he now wants to understand how many truly happy couples are there in the world. For a given n he wants to know how many couples exist on the first nnhuman beings (i.e. the first nn Fibonacci numbers) such that all conditions above hold true.

Input

The first line of the input represents the number of test cases. Each case consists of a single integer n (1≤n≤105) per line.

Output

For each case print the number of perfect couples.

Example

6
1
4
8
17
20
25

0
3
5
11
13
17

题目链接：https://vjudge.net/contest/345791#problem/H

试题解析

题目要求在前n个斐波那契数当中有多少对x，y同时满足（x+y）mod2==1，gcd(x，y)==1，x+y是一个斐波那契数。

因为x+y要是一个斐波那契数，有斐波那契数的性质F_k+2=F_k+1+F_k可以知道x和y一定是两个连续的斐波那契数。

同时连续的两个斐波那契数一定是互质的，所以我们只需要判断x+y是不是2的倍数就好了。

斐波那契数组的前两个数都是1，我们又知道奇数+奇数=偶数，偶数+奇数=奇数。

发现斐波那契数组的性质：奇，奇，偶，奇，奇，偶，奇，奇，偶.......

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define RG register
#define CLR(arr,val) memset(arr,val,sizeof(arr))
typedef long long ll;
const double pi=acos(-1.0);
const int maxn=500005;
int ans[maxn];

void inti()
{
	ans[3]=2;
	ans[4]=3;
	for(int i=5;i<maxn;i++)
	{
		if((i%3&&(i+1)%3)||i%3==0) {
			ans[i]=ans[i-1]+1;
		}else {
			ans[i]=ans[i-1];
		}
	}
}

int main(void)
{
	inti();
	int t;
	scanf("%d",&t);
	while(t--) {
		int n;
		scanf("%d",&n);
		printf("%d\n",ans[n]);
	}
    return 0;
}

原文地址：https://www.cnblogs.com/bqyb/p/11966594.html