ZZUOJ - 1241 - 斐波那契數

鄭州大學第八屆ACM大學生程式設計競賽正式賽

C.斐波那契數

Description

xq最近迷戀上了斐波那契數列，因為當n趨向于無窮大時，後一項與前一項的比值越來越逼近黃金分割0.618。不過令xq不開心的是，斐波那契數的增長速度太快了，以至于當n很大時，用計算機中的32位整數甚至64位整數都已經不能表示這個數了。基于這個原因，xq遇到了這個難題，xq想要知道第K（0<=K<=10^10000）項斐波那契數是奇數還是偶數，因為K太大了，xq不知道怎麼解決這個問題，現在xq想讓你解決這個問題。斐波那契數列是如下的一個數列，0,1，1，2，3，5……，其通項公式為F（n）=F（n-1）+F（n-2），（n>=2） ，其中F（0）=0，F（1）=1。

Input

第一行，T，表示有1<=T<100個測試樣例。

接下來T行，每行一個資料K（0<=K<=10^10000），表示要判定的是哪一項。

Output

如果第K項是偶數，輸出YES，否則輸出NO。

Sample Input

2

1

Sample Output

YES

NO

思路：就是一道找規律題，把斐波那契數列列出來後會發現，序号隻要是3的倍數就是偶數，那題目就變成了判斷給的數字是不是3的倍數，題目給的10^10000，這其中有一個小結論，如果一個很大的數字，把它的各個位數相加如果是三的倍數，那麼這個數就是3的倍數，一下子題目就簡單躲了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while(t--){
        char str[];
        scanf("%s", str);
        int len = strlen(str);
        int sum = ;
        for(int i = ; i < len; i++){
            sum += str[i]-'0';
        }
        if(sum% == )  printf("YES\n");
        else    printf("NO\n");
    }
    return ;
}