首页 > 代码库 > HDU 1005
HDU 1005
这道题类似数学中的找规律
不断往前计算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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。