HDU1005 Number Sequence

HDU1005 Number Sequence
对于公式f[n]=A* f[n-1]+B* f[n-2]，因为对于f[n-1]或者f[n-2] 的取值只有0、1、2、3、4、5、6这7个数，A、B又是固定的，所以只有7*7=49种可能值。
由该关系式得知每一项只与前两项发生关系，所以当再次连续出现1、1时，就找到了循环节mod
在输出答案时还要注意n%mod=0的情况。

1//0ms
2#include <bits/stdc++.h>
3using namespace std;
4int a[50],A,B,n,i,mod;
5int main()
6{
7   
8   
9   
10    while(cin>>A>>B>>n&&A&&B&&n)
11    {
12   
13   
14   
15        a[1]=a[2]=1;
16        for(i=3;i<=49;i++)
17        {
18   
19   
20   
21            a[i]=(A*a[i-1]+B*a[i-2])%7;
22            if(a[i]==1&&a[i-1]==1)break;
23        }
24        mod=i-2;n=n%mod;
25        if(n==0) printf("%d\n",a[mod]);//注意n%mod=0的情况
26        else printf("%d\n",a[n]);
27    }
28    return 0;
29}

本文同步分享在 博客"nefu_ljw"（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。