hdu1005 Number Sequence（寻找循环节）

阅读量：5886 次

发布时间：2019-06-19

本文共 1466 字，大约阅读时间需要 4 分钟。

主题链接：

题意：

就是给了一个公式，然后求出第n项是多少。。。

思路：

题目中n的范围实在是太大，所以肯定直接递推肯定会超时，所以想到的是暴力打表，找循环节，可是也不是那么easy发现啊，所以这时候分析一下，由于最后都会mod7，所以总共同拥有7X7总情况，即A 0，1,2,3,4,5,6,7。B也是如此，所以循环节为49，这么这个问题就攻克了。

。。

题目：

Number Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 105674 Accepted Submission(s): 25691

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

Recommend

JGShining | We have carefully selected several similar problems for you:

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #define eps 1e-9#define ll long long#define INF 0x3f3f3f3fusing namespace std;#define mod 7const int maxn=1000+10;int a[maxn];int A,B,n;int main(){ while(~scanf("%d%d%d",&A,&B,&n)) { if(A==0&&B==0&&n==0) return 0; a[1]=1,a[2]=1; for(int i=3;i<=100;i++) a[i]=(A*a[i-1]+B*a[i-2])%mod; printf("%d\n",a[n%49]); } return 0;}

转载地址：http://nqrix.baihongyu.com/

你可能感兴趣的文章