求解一个类似于斐波拉契数列的有关问题

求解一个类似于斐波拉契数列的问题
Problem Description
A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

Output
For each test case, print the value of f(n) on a single line.

Sample Input
1 1 3
1 2 10
0 0 0

Sample Output
2
5

我的程序是这样的，但提交到OJ却显示Memory Limit Exceeded，超过内存限制，求各位大神教教小弟怎么修改？还有这种类似问题应该怎么做才能避免超内存呢？
#include<stdio.h>
int k[100000001];
int main()
{
  int a,b,n,i;
  while(scanf("%d %d %d",&a,&b,&n)==3,a!=0||b!=0||n!=0)
  {
  k[0]=1;
  k[1]=1;
  for(i=2;i<100000001;i++)
  {
  k[i]=(a*k[i-1]+b*k[i-2])%7;
  }
  printf("%d\n",k[n-1]);
  }
  return 0;
}


------解决方案--------------------
这种题最好用递归吧，你那个好浪费内存空间，int k[100000001]这么大的内存。
下面是我找自己想法写的
[code=C/C++][/code]

#include<stdio.h>

int a = 0;
int b = 0;
int get_caculate(int n)
{
if(n==1 || n==2)
return 1;
else
/*f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7 */
return (a*get_caculate(n-1) + b*get_caculate(n-2)) % 7;
}

int main()
{
int n;
while(scanf("%d %d %d",&a,&b,&n)==3,a!=0||b!=0||n!=0)
{
printf("%d", get_caculate(n));
}

return 0;
}
自己看了下运行结果，能对上结果。
------解决方案--------------------
这里有个稍微高效的算法，即使n很大，最多循环49次
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int flag[7][7];
int f[100];
int a, b, n;

int func()
{
int i, circle, ipos;

a %= 7, b %= 7;
memset(flag, 0, sizeof(flag));
flag[1][1] = 2;
f[1] = 1, f[2] = 1;

i = 3;
f[i] = (f[i - 1] * a + f[i - 2] * b) % 7;
while (flag[f[i - 1]][f[i]] == 0)
{
flag[f[i - 1]][f[i]] = i; 
i++;
f[i] = (f[i - 1] * a + f[i - 2] * b) % 7;
}

ipos = flag[f[i - 1]][f[i]];
circle = i - ipos;

if (n <= ipos)
return f[ipos];
return f[ipos + (n - ipos) % circle];
}

int main()
{
while (scanf("%d %d %d", &a, &b, &n) && (a != 0 || b != 0 || n != 0))
printf("%d\n", func());
return 0;
}

------解决方案--------------------
楼主的int k[100000001];直接就把栈用光了，所以程序根本无法运行。

楼主的主要思想是对的，
建议方法：在用户输入了A、B、N后，使用malloc动态申请内存。而不是直接使用全局变量。

如果还是超过内存，建议减少缓存个数，例如只使用三个int来保存f(n-1),f(n-2),f(n)，而不是使用100000001个int。

如果超过运算时间，楼主可以尝试使用《组合数学》中的推导，看能不能推导出直接函数表达式。（个人组合数学学得太差……呜呜）
------解决方案--------------------
#include<stdio.h>
void main()
{
long a,b,n,i;
int f1,f2,f3;

while(1)
{
printf("Input A,B,N:");
scanf("%ld %ld %ld",&a,&b,&n);
if(a==0&&b==0&&n==0)
break;
if(a<1 || b>1000 || n<1 ||n>100000000)
{
printf("Input Error!\n 1<=A, B <=1000, 1 <= n <=100,000,000\n");
continue;
}

f1=1;
f2=1;
if(n==1)