首页 > 代码库 > HDU 1005

HDU 1005

2024-08-09 04:16:08   221人阅读

这道题类似数学中的找规律

不断往前计算f[n]，直到出现一组数据（两个相邻的数)和前面的(两个相同的数)相同，那么就形成了循环

 

因为始终mod7，那么每个数字只有0~6  7种可能，两个为一组，最多49种可能，也就是往前计算最坏情况也只要计算49次就好了

 

 1 #include <cstdio> 2 #include <cstring> 3  4 using namespace std; 5 #define N 100 6 int f[N]; 7  8 int main() 9 {10    // freopen("a.in" , "r" , stdin);11     int a , b , k;12     f[0] = f[1] = f[2] = 1;13     while(~scanf("%d%d%d" , &a , &b , &k)){14         if(a == 0 && b == 0 && k == 0) break;15         int cnt = 2;16         int l , len;17         while(1){18             cnt++;19             f[cnt] = (a * f[cnt - 1] + b * f[cnt - 2]) % 7;20             int flag = 0;21             for(int i = cnt-1 ; i>=2 ; i--){22                 if(f[i] == f[cnt] && f[i-1] == f[cnt-1]){23                     l = i-1 , len = cnt - i;24                     flag = 1;25                    // printf("the same : %d  %d\n",len,l);26                    // for(int i = 1 ; i<=cnt ; i++) printf("%d " , f[i]);27                     break;28                 }29             }30             if(flag) break;31         }32         if(k <= cnt) printf("%d\n" , f[k]);33         else{34             int index = k-l+1;35             index = (index-1) % len; //因为是从下标1开始，首先要-1，这样mod后得到0~len-1的范围，实际上为1~len，所以后面再加一36             index = index + l;37             printf("%d\n" , f[index]);38         }39     }40     return 0;41 }

 

HDU 1005


联系
我们