Fibonacci数列简单的算法

问题遇到的现象和发生背景

运行超时，有啥简单的方法

用代码块功能插入代码，请勿粘贴截图

#include
long long function(long long n);
main()
{
long long n,y;
scanf("%lld",&n);
if(n<1||n>1000000)
return 0;
if(n==1||n==2)
y=1;
else y=function(n);
printf("%lld",y);
}
long long function(long long n)
{
long long f;
if(n==1||n==2)
f=1;
else f=function(n-1)+function(n-2);
return f;
}

直接循环算，递归开销大，费时间。
n范围太大，longlong装不下

int main()
{
    long long n, y = 1, a = 1, b, i;

    scanf("%lld", &n);
    if (n < 1 || n > 1000000)
        return 0;

    for (i = 3; i <= n; i++)
    {
        b = y;
        y += a;
        a = b;
    }
    printf("%lld", y);
}