首页 > 代码库 > 找规律/hdu 1005 Number Sequence

找规律/hdu 1005 Number Sequence

2024-07-27 10:01:47   214人阅读

题意

　　给出a,b,n，已知f[1]=f[2]=1，f[i]＝(a*f[i-1]+b*f[i-2]) mod 7

　　输出f[n]

　　数据范围 1 <= A, B <= 1000, 1 <= n <= 100,000,000

分析

　　首先，直接求..肯定是不行的 会tle 会mle 

　　但是可以找到规律，例如对a=1,b=1 这个数据，有

　　f1=1　　f2=1　　f3=3

　　f4=5　　f5=4　　f6=0

　　f7=1　　f8=1　　f9=3

　　f10=5　 f11=4　 f12=0

　　????

　　我们会发现有一定的规律：每当遇到1, 1 时，就代表一次新的周期，所以我们只需求出周期t以及一个周期的答案，f[n mod t]即为答案

　　关于利用循环查找周期：保险起见，我循环到10000来查找，但是过后查看别人的题解，发现循环到49即可，但具体证明未能找到

 

Accepted Code

 1 /* 2     PROBLEM:hdu1005 3     AUTHER:NicoleLam 4     MEMO:找规律 5 */ 6  7 #include<cstdio> 8 using namespace std; 9 const int N=100;10 int f[N];11 12 int main()13 {14     int a,b,n;15     scanf("%d%d%d",&a,&b,&n);16 17     while ((a!=0) && (b!=0) && (n!=0))18     {19         f[1]=1,f[2]=1;20         int i;21         for (i=3;i<100;i++)22         {23             f[i] = (a*f[i-1] + b*f[i-2])  %  7;24 25             if ( f[i-1]==1 && f[i]==1) break;26         }27         n=n%(i-2);28         f[0]=f[i-2];29         printf("%d\n",f[n]);30         scanf("%d%d%d",&a,&b,&n);31     }32     return 0;33 }

 

找规律/hdu 1005 Number Sequence


联系
我们