HDU 1021 Fibonacci Again

简介: Fibonacci Again Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 58267    Accepted Submission(...

Fibonacci Again

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 58267    Accepted Submission(s): 27275


Problem Description
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).
 

 

Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).
 

 

Output
Print the word "yes" if 3 divide evenly into F(n).

Print the word "no" if not.
 

 

Sample Input
0
1
2
3
4
5
Sample Output
no
no
yes
no
no
no
Author
Leojay
分析:有两种方法:第一种是找规律,除4余2的就输出yes。否则no.这种方法确实很神奇,想不到没关系!先给出第一种方法的AC代码
 1 #include<stdio.h>
 2 int main()
 3 {
 4     int n;
 5     while(scanf("%d",&n)!=EOF)
 6     {
 7         if(n%4==2) printf("yes\n");
 8         else
 9             printf("no\n");
10     }
11     return 0;
12 }

第二种方法,直接取对3取模!

由同余式的基本性质:

1)自反性:a = a( mod m)。

以及同余式的四则运算法则:

1)如果 a =b( mod m)且 c = d( mod m),则 a +c = (b + d)( mod m)。

可知,F(n) = F(n) ( mod m) = ( F(n-1) +F(n-2) )( mod m)。

下面给出AC代码:

 

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 int f[1000100];
 5 int main()
 6 {
 7 f[0]=1; f[1]=2;
 8 int n;
 9 while(scanf("%d",&n)!=EOF)
10 {
11 for(int i=2;i<=n;i++)
12 {
13 f[i] = (f[i-1]+f[i-2])%3;
14 }
15 if(f[n]%3==0)
16 printf("yes\n");
17 else
18 printf("no\n");
19 }
20 return 0;
21 }

 

 

 

目录
相关文章
|
4月前
辗转相除法
【10月更文挑战第21天】辗转相除法。
50 2
|
8月前
|
C++
【PTA】L1-046 整除光棍(C++)
【PTA】L1-046 整除光棍(C++)
96 1
|
9月前
PTA-第4章-11 判断素数
```markdown 程序需处理不超过10个正整数,每个数不大于1000000。对于每个数,若为素数则输出&quot;Yes&quot;,否则输出&quot;No&quot;。 输入示例: ``` 2 11 111 ``` 输出示例: ``` Yes No ```
59 8
|
9月前
|
算法
辗转相除法求最大公约数
辗转相除法求最大公约数
|
9月前
PTA-求指定范围内的素数
求指定范围内的素数
110 0
|
9月前
PTA-求100以内的素数
求100以内的素数
74 0
|
Java
hdu 1262 寻找素数对
hdu 1262 寻找素数对
42 0
|
算法 Java
欧几里得算法(GCD, 辗转相除法)
欧几里得算法(GCD, 辗转相除法)
求最小公倍数!
求最小公倍数!
118 0
辗转相除法__约分
辗转相除法__约分
96 0