代码输出时间超限怎么解决？

问题:
小D这几天喜欢上了斐波那契数列！我们都知道，斐波那契数列的递归定义是：
(F1=1，F2=1，Fn=Fn-1+Fn-2(n≥3))，现在他想知道数列的第n项是奇数还是偶数，请你帮他算一算。
输入
输入数据包含多组测试数据，每个测试实例占一行，每行为一个数，表示斐波那契数列的第n项(1≤n<10^9)
输出
输出斐波那契数列的第n项是奇数还是偶数，奇数输出even，偶数输出odd，对于每个测试实例，输出一行。
代码:
#include <stdio.h>
int F(int n)
{
if(n==1||n==2)
return 1;
else
return F(n-1)+F(n-2);
}

int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(F(n)%2!=0)
printf("even\n");
else
printf("odd\n");
}
return 0;
}
这个代码时间超限，有什么解决办法吗？

假设重复输入一个大数，那么每次都会对这个大数进行F(n)求解，即每一次你都是从0开始，所以你可以用数组arr暂存F(n)的解，如果arr[n] = 0，则求解arr[n]=arr[n-1]+arr[n-2]，否则返回arr[n]

你为什么要写个while一直循环，题目要求你输入一个数，计算，然后就结束了啊
你这输出完还不结束，还要求继续输入，不超时怎的