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
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1021
分析:有两种方法:第一种是找规律,除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 }