In Africa there is a very special species of bee. Every year, the female bees of such species give birth
to one male bee, while the male bees give birth to one male bee and one female bee, and then they die!
Now scientists have accidentally found one “magical female bee” of such special species to the effect
that she is immortal, but still able to give birth once a year as all the other female bees. The scientists
would like to know how many bees there will be after N years. Please write a program that helps them
find the number of male bees and the total number of all bees after N years.

Input

Each line of input contains an integer N (≥ 0). Input ends with a case where N = −1. (This case
should NOT be processed.)

Output

Each line of output should have two numbers, the first one being the number of male bees after N
years, and the second one being the total number of bees after N years. (The two numbers will not
exceed 232.)

Sample Input

1
3
-1

Sample Output

1 2
4 7

简单推导了一下，发现是类斐波那契，提前打表，注意一下long long数据类型，AC代码

#include<bits/stdc++.h>
using namespace std;
long long a[100000005];
int main()
{
    a[0] = 1;
    a[1] = 2;
    for(int i = 2; i < 100000004; i++)
        a[i] = a[i-1] + a[i-2] + 1;
    int n;
    while(~scanf("%d",&n) && n!= -1){
        if(n < 100000004)
            printf("%lld %lld\n",a[n-1],a[n]);
        else{
            long long fir,sec,thr;
            fir = a[100000002];
            sec = a[100000003];
            n -= 100000003;
            while(n){
                thr = fir + sec + 1;
                fir = sec;
                sec = thr;
                n--;
            }
            printf("%lld %lld\n",fir,sec);
        }
    }
    return 0;
}