CDZSC_2015寒假新人（2）——数学 E

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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

 

 

 

 

思路：这题我是通过用超时的代码观察规律做的，这题是有规律的，他会有周期的，而且所以我们只要在只要找到1格连在一起的1就可以找到周期了。。因为周期中间不可能会有连续的1，如果有的话那所以数都是1的。。。。。所以输出f[n%i-2]的数就好了，还有注意整除i-2是输出f[i-2]

 

发2张图看看吧

 

 

其实后来师兄告诉我求mod是有循环节的，mod7的循环节是7*7=49。。。。

 

 

 

 

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
#ifdef CDZSC_OFFLINE
    //freopen("in.txt","r",stdin);
#endif
    int f[10000];
    int a,n,b,i;
    while(scanf("%d%d%d",&a,&b,&n)&&a!=0&&b!=0&&n!=0)
    {
        f[1]=1;
        f[2]=1;
        for(i=3; i<10000; i++)
        {
            f[i]=(a*f[i-1]+b*f[i-2])%7;
            if(f[i]==1&&f[i-1]==1)
            {
                break;
            }
        }
        if(n%(i-2)==0)
        {
            printf("%d
",f[i-2]);
        }
        else
        {
            printf("%d
",f[n%(i-2)]);
        }
    }
    return 0;
}