1005 Number Sequence

时间限制: 1 Sec  内存限制: 60 MB

题目描述

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). 

输入

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. 

输出

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

解题思路

显然，这是一个找周期的问题。

我们很容易推出，一定有周期，而且最小周期不超过49，（在下面，都假设a和b小于7，即已经%7），而且，如果a、b不全为0，那么一定是从第1项开始循环的，当a=b=0时，不是从第1项开始，而是从第3项开始循环。我一开始的方法是，对于每组给的a、b，求出最小正周期

代码：

#include <stdio.h>
/*找周期*/
int period(int a, int b)
{
    int t = 0, f1 = 1, f2 = 1, temp;
    if (a == 0 || b == 0)
        return 12;
    if ((a + b) % 7 == 1)
        return 1;
    while (1)
    {
        temp = (a * f1 + b * f2) % 7;
        f2 = f1;
        f1 = temp;
        t++;
        if (f1 == 1 && f2 == 1)     /*再次遇到f1 = 1，f2 = 1的时候跳出*/
            break;
    }
    return t;
}
int main()
{
    int a, b, n, f1, f2, temp;
    while (scanf("%d%d%d", &a, &b, &n), a, b, n)
    {
        if (a % 7 == 0 && b % 7 == 0)
        {
            printf("%d\n", n < 3);
            continue;
        }
        f1 = 1, f2 = 1;
        if (n > 20)
            n = (n - 20) % period(a % 7, b % 7) + 20;
        if (n > 2)
            n -= 2;
        else n = 0;
        while (n--)
        {
            temp = (a * f1 + b * f2) % 7;
            f2 = f1;
            f1 = temp;
        }
        printf("%d\n", f1);
    }
    return 0;
}

我发现网上有有很多这道题的题解，代码很短，就看了一下，发现他们是直接以48为周期，甚至还有很多人说49是周期。。。

但是我枚举了a和b（一共也就49种情况），发现周期并不是48。

代码：

int main()
{
    for (int i = 0; i < 7; i++)
    {
        for (int j = 0; j < 7; j++)
            printf("%d ", period(i, j));
        printf("\n");
    }
    return 0;
}

结果：

12 12 12 12 12 12 12
12 16 6 24 48 21 6
12 6 48 6 48 24 1
12 16 48 42 6 1 8
12 16 48 21 1 6 8
12 6 48 1 48 24 14
12 16 1 24 48 42 3

很明显，有14、21、42的存在，显然48不是周期！所以说，应该是OJ给的测试数据很水，有很多代码都浑水摸鱼了。但336一定是周期，所以就可以写出代码了。

代码：

#include <stdio.h>
int main()
{
    int a, b, n, f1, f2, temp;
    while (scanf("%d%d%d", &a, &b, &n), a, b, n)
    {
	if (a % 7 == 0 && b % 7 == 0)
	{
	    printf("%d\n", n < 3);
	    continue;
	}
	f1 = 1, f2 = 1;
	n = (n + 333) % 336 + 1;
	while (n--)
	{
            temp = (a * f1 + b * f2) % 7;
	    f2 = f1;
	    f1 = temp;
	}
	printf("%d\n", f1);
    }
    return 0;
}