首页 > 代码库 > HDOJ 1005 Number Sequence

HDOJ 1005 Number Sequence

2024-07-04 15:38:45   228人阅读

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
这个题目要求计算指定的数列，开始计算时直接for循环来计算要求的数据，但是提交上去后发现超时了。
后来发现这个题目的数列肯定是有周期的，只要求出这个周期即可解决这个问题....但是其周期也是从第3项开始，如果从第一项计算时提交上去出现WA，网上查找资料后发现，这个数列的周期要从第3项开始。如果从第一项开始时，7、7、10时，其周期是1、1、0、0、0.......这样不可能计算出周期，所以应该从第3项开始计算其周期。
 1 #include <iostream>
 2 using namespace std;
 3 #define Max 100
 4 int main()
 5 {
 6     unsigned int A,B,n,result,fn[Max]={0};
 7     int i=0;
 8     unsigned int f1,f2;
 9     cin>>A>>B>>n;
10     while(A||B||n)
11     {
12         f1=1;
13         f2=1;
14         fn[0]=(A*f1+B*f2)%7;
15         fn[1]=(A*fn[0]+B*f2)%7;        
16         for(i=2;i<=n;i++)
17         {
18             fn[i]=(A*fn[i-1]+B*fn[i-2])%7;
19             if(fn[i-1]==fn[0]&&fn[i]==fn[1])
20             {
21                 result=fn[(n-3)%(i-1)];//求出周期
22                 break;
23             }
24         }        
25         if(n==1||n==2)
26         {
27             cout<<f1<<endl;
28         }
29         else
30         cout<<fn[(n-3)%(i-1)]<<endl;
31         cin>>A>>B>>n;
32     }
33     return 0;
34 }

 心得：计算这种数列时，必须要对其周期进行计算，这样能够节省大量时间....


联系
我们