A number sequence is defined as:
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)

输入格式
There are multiple lines of input. Every line is a test case. Each test case contains 3 integers A, B, and n on a single line (1 <= A, B <= 1000, 1 <= n <= 10000). Three zeros signal the end of input and this test case is not to be processed.
输出格式
For each test case, print the value of f(n) on a single line.
样例输入
 将样例输入复制到剪贴板
1 1 3
1 2 10
0 0 0样例输出
2
5
这是我的代码：
#include<stdio.h>
int fab (int a,int b,int c);
int main()
{
    int a,b,c;
    while(1)
    {
        scanf("%d %d %d",&a,&b,&c);
        if(a==0&&b==0&&c==0)
            break;
        else
        {
            printf("%d\n",fab(a,b,c));
        }
    }
}
int fab (int a,int b,int c)
{
    if(c==1||c==2)
    return 1;
   
    else  return (a*fab(a,b,c-1)+b*fab(a,b,c-2))%7;

}
能不能优化一下？递归会超时啊。谢谢。

你怎么知道会超时，怎么看出来的，没在程序中写检测时间的代码啊？是不是有其他的途径？

抱歉，检测时间是1s。

显然DP， 这个递归显然耗时很大。

那怎么优化啊？

这是一个周期函数，周期不超过49。你需要做的是找到这个周期及循环的起始位置（这类似于三角函数中的初相角）

呵呵，哪位能证明一下它为什么是一个周期函数么？

f(n-1) 有7中结果,f(n-2)有 7种结果，可得共49种。
推论:
f(n)  == f[n%i] (i是周期）

[ 本帖最后由 Devil_W 于 2012-2-10 22:19 编辑 ]

#include<stdio.h>
#define M 52
int main()
{ 
    int a,b,n,i,f[M]={0,1,1},t; 
    while(scanf("%d %d %d",&a,&b,&n),a!=0||b!=0||n!=0)
    {
        a%=7;b%=7; 
        for(i=3;i<M;i++)
        { 
            f[i]=a*f[i-1]+b*f[i-2]; 
            f[i]%=7; 
            if(f[i-1]==f[3]&&f[i]==f[4]&&i>4) break;
        } 
        t=i-4; 
        if(n<4)printf("%d\n",f[n]);        
        else printf("%d\n",f[(n-4)%t+4]);
    } 
    return 0;
}

谢谢
原来优化 在很大程度上是  找到一种新的解题方法   
数学要补课啦
谢谢

呵呵，虽然不是严谨的证明，不过就是这么回事。