递推数列

题目描述

给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。 求第k个数对10000的模。

输入描述:

输入包括5个整数：a0、a1、p、q、k。

输出描述:

第k个数a(k)对10000的模。

输入

20 1 1 14 5

输出

8359

---

思路分析

 将每一次得到的结果记录下来，再进行递推。

  最重要的是需要将每一个递推数进行截断，即每一次都要进行取模，这样才不会超过内存限制。

#include <stdio.h>

int main()
{
    int a0,a1,p,q,k;
    
    while(scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k)!= EOF)
    {
        long re = 0;
        for(int i=2;i<=k;i++)
        {
            re = (a1*p+a0*q)%10000;
            a0 = a1;
            a1 = re;
        }
        re = re%10000;
        printf("%ld",re);
    }
    return 0;
}