1005：Number Sequence（hdu，数学规律题）

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

Author

CHEN, Shunbao

Source

ZJCPC2004

 #include<iostream>

 using namespace std;

 int main()

 {

     int f[];

     int a, b, n;

     while (cin >> a >> b >> n, a !=  && b !=  && n != )

     {

         int i;

         f[] = , f[] = ;

         for (i = ; i < ; i++)

         {

             f[i] = (a*f[i - ] + b * f[i - ]) % ;

             if (f[i] ==  && f[i - ] == ) break;

          }

         i -= ;

         if (i > n)

         {

             cout << f[n] << endl;

             continue;

         }

         n = n % i;

         if (n == ) n = i;

         cout << f[n] << endl;

     }

     return ;

 }

大佬代码：http://www.cnblogs.com/kuangbin/archive/2011/07/26/2117381.html

#include<stdio.h>

int main()

{

    //freopen("test.in","r",stdin);

    //freopen("test.out","w",stdout);

    int A,B,i;

    long n;

    int f[];

    f[]=f[]=;

    while(scanf("%d %d %ld",&A,&B,&n))

    {

        if(A==&&B==&&n==) break;

        int cnt=;

        for(i=;i<=;i++)//打表找到周期

        {

            f[i]=(A*f[i-]+B*f[i-])%;

            if(f[i]==&&f[i-]==)break;

            if(f[i]==&&f[i-]==){cnt=;break;}//这里有个小陷阱，如果A=7，B=7则后面都为0了

        }

        if(cnt){printf("0\n");continue;}

        if(i>n){printf("%d\n",f[n]);continue;}

        i-=;//i为周期

        n%=i;

        if(n==)n=i;

        printf("%d\n",f[n]);

    }

    return ;   

}

这题完全参考大佬的代码改良；

凉凉；；；；；；；；；

数据量小，一些不合适的没在测试数据不在里面

巴特西

1005：Number Sequence（hdu，数学规律题）

最新文章

热门文章