Fibonacci Again

开发者子格技术 2022年11月16日

0 收藏 461 点赞 3,879 浏览 752 个字

Problem DescriptionThere are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2). InputInput consists of a sequence of lines, each containing an integer n. (n < 1,000,000). OutputPrint the word “yes” if 3 divide evenly into F(n).

Print the word “no” if not.

Sample Input012345 Sample Outputnonoyesnonono

做这道题的思路来自hau oj 的另一道题

1005

Number Sequence

是一个周期的问题

/*思路如下，题目最终是要判断能否被3整除，那么在计算每一个 f（n）时，可以先对 3 求余，

那么，问题就转化为题号：1005 由于对 3 求余，那么结果就被控制在范围 0—2 ，当满足

f（n-1)=f（0）=7%3=1 并且 f（n）=f（1）=11%3=2时。break循环，而不必要算出全部 f（n）

此时以 i-2 作为一个周期那么 f（n）=f（n%(i-2)) 若f（n）==0 说明原f（n）能被3 整除*/

#include<cstdio>
int are[];
int main()
{
    int i;
    are[]=;
    are[]=;
    for(i=; i<; i++)
    {
        are[i]=(are[i-]+are[i-])%;
        if(are[i]==&&are[i-]==)
            break;
    }    int n;
    while(scanf("%d",&n)!=EOF)
    {
        n=n%(i-);
        if(are[n]==) printf("yes\n");
        else printf("no\n");    }
    return ;
}