Problem 1049 - 斐波那契数

Description

       斐波那契数列是如下的一个数列，0,1，1，2，3，5……，其通项公式为F（n）=F（n-1）+F（n-2），（n>=2） ,其中F（0）=0，F（1）=1，你的任务很简单，判定斐波契数列的第K项是否为偶数，如果是输出YES，否则输出NO

Input

第一行，T，表示有T个测试样例。
接下来T行，每行一个数据K（0<=K<=10^10000），表示要判定的是哪一项。

Output

如果第K项是偶数，输出YES，否则输出NO。

Sample Input

2
0
1

Sample Output

YES
NO

Hint

64-bit interger is not enough for 10^10000

Source

FZ

分析：该题目关键在于大数的存储，可以采用字符数组存储整数，然后可观察T(n)序列从0开始实际上是一个以3为周期的 “偶奇奇”的重复序列。
T(0) = 0 = YES
T(1) = 1 = NO
T(2) = 1 = NO
T(3) = 2 = YES
T(4) = 3 = NO
T(5) = 5 = NO
T(6) = 8 = YES
……

可见，当n为3的倍数（包括0倍)时，则T(n)偶数，否则是奇数。
这就需要用到一个小技巧了：任何10进制数，如果各位数字的和能被3整除，则该数整体能被三整出，例如，
12 => 1+2=3,3能被3整除，所以12能被3整除
1293 => 1+2+9+3 = 15，15能被3整除，所以1293能被3整除

C代码：

#include<stdio.h>
#include<string.h>
int a,b,c,d,e,sum;
char s[10005];

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
          sum=0;
          scanf("%s",&s);
          d=strlen(s);
          for (a=0;a<d;a++) sum=sum+(s[a]-'0');
          if (sum%3==0) printf("YES\n"); else printf("NO\n");
    }
}
#include<stdio.h>
#include<string.h>
char s[10010];
int main()
{
    int n,i,sum,len;
    while(scanf("%d",&n)!=EOF)
    {
        while(n--)
        {
            sum=0;
            scanf("%s",s);
            len=strlen(s);
            for(i=0;i<len;i++)
                sum+=s[i]-'0';
            if(sum%3==0) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

C++代码：

#include <string>
using namespace std;

bool IsEvent(string bigInt)
{
    int sum = 0;
    for (size_t i=0; i<bigInt.size(); ++i)
    {
        sum += (bigInt[i] - '0');
    }

    return (sum % 3)==0;
}

#include <iostream>
int main()
{
	int n;
	string bigInt;
	cin>>n;
	for (int i=0; i<n; ++i)
	{
		cin>>bigInt;
		cout<<(IsEvent(bigInt) ? "YES" : "NO")<<endl;
	}
	return 0;
}