学步园

根据同余问题的一个定理可知：F(n) ≡(F(n-1) + F(n-2))%3;

F(n)%3的值等于(F(n-1)%3 + F(n-2)%3)%3;

#include <iostream>

using namespace std;

const int MAXN = 1000010;

int d[MAXN];
void do_Pre()
{
     int i;
     d[0] = 7 % 3;
     d[1] = 11 % 3;
     for(i = 2; i < MAXN; ++i)
     {
          d[i] = (d[i-1]%3 + d[i-2]%3)%3;
     }

}

int main()
{
     int n;
     do_Pre();
     while(cin>>n)
     {
          if(!d[n])
               cout<<"yes"<<endl;
          else
               cout<<"no"<<endl;
     }
    return 0;
}