HDOJ 1021 Fibonacci Again 【数论】

题目链接

---

题目就是重新定义了一个斐波那契数列

给定数列的某一项 如果该项的斐波那契数可以被3整除输出yes

否则输出no

---

1、【两个数的和】的【各位之和】 == 两个【数的各位之和】的【和】

2、能被3整除的数的【各位之和】也能被3整除

3、所以，得出公式 ( a + b ) % 3 = ( a % 3 + b % 3) % 3

然后预处理做个表就可以了

---

#include
     
      #include
      
       using namespace std;#define clr(c) memset(c, 0, sizeof(c));const int INF = 0x3f3f3f3f;typedef long long ll;int n;int fib[1000005];void Pre(){    fib[0] = 7 % 3;    fib[1] = 11 % 3;    for(int i = 2; i <= 1000000; i++){        fib[i] = ((fib[i-1] % 3) + (fib[i-2] % 3)) % 3;    }}int main(){    Pre();    while(~scanf("%d", &n)){        if(fib[n]) puts("no");        else puts("yes");    }    return 0;}
      
     

版权声明：本文为博主原创文章，未经博主允许不得转载。