NEFU 115

【类型】

斐波那契+lcm+循环节<-找规律

【题目来源】

NEFU-115-斐波那契的整除

【分析】

输入数据有若干组,每组数据包含一个整数n(1< n <1000000000)。

从这句中我们得以看出暴力不是一个好方法,考虑循环节,发现当n%4==0时f(n)能被3整除;n%6==0时,f(n)能被4整除;然后由lcm得出f(n)能被12整除,当且仅当n%12==0(lcm(4,6)).

【验证】
打印发现循环节为 3 4 3 12

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int main(){
    LL a,b,c;
    a=1,b=1;
    for(int i=3;i<=50;++i){
        c=a+b,a=b,b=c,cout<<i<<": "<<c<<" ";
        if(c%3==0)cout<<" 3";
        if(c%4==0)cout<<" 4";
        cout<<endl;
    }
    return 0;
}

【Code】

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(!(n%12))
            cout<<"YES\n";
        else if(!(n%4))
            cout<<"3\n";
        else if(!(n%6))
            cout<<"4\n";
        else
            cout<<"NO\n";
    }
    return 0;
}