NEFU 115 斐波那契的整除

已知斐波那契数列有如下递归定义，f(1)=1,f(2)=1, 且n>=3,f(n)=f(n-1)+f(n-2)，它的前几项可以表示为1， 1，2 ，3 ，5 ，8，13，21，34…，现在的问题是想知道f(n)的值是否能被3和4整除，你知道吗？

输入数据有若干组，每组数据包含一个整数n（1< n <1000000000）。

对应每组数据n，若 f(n)能被3整除，则输出“3”； 若f(n) 能被4整除，则输出“4”；如果能被12整除，输出“YES”；否则输出“NO”。

4
6
7
12

3
4
NO
YES

这道题数据量很大，直接计算必然溢出，因此考虑是否有循环节

斐波那契数对3的余数：d(n)=(d(n-1)+d(n-2))%3

写出来即为：1 1 2 0 2 2 1 0 1 1 2 ……

观察到f(n)能被3整除当且仅当n能被4整除

同理可发现f(n)能被4整除当且仅当n能被6整除

所以f(n)能被12整除当且仅当n能被4和6的最大公约数（即12）整除

代码很容易写出~~

[C++]

1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     long n;
 8     while(cin>>n)
 9     {
10         if(n%12==0)
11             cout<<"YES"<<endl;
12         else if(n%4==0)
13             cout<<"3"<<endl;
14         else if(n%6==0)
15             cout<<"4"<<endl;
16         else
17             cout<<"NO"<<endl;
18     }
19 
20     return 0;
21 }

原文链接: https://www.cnblogs.com/lzj-0218/archive/2013/04/30/3051546.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍