寒假集训附加题目题解报告（1）——数列

最新推荐文章于 2025-02-07 02:28:48 发布

zhengnanlee

最新推荐文章于 2025-02-07 02:28:48 发布

阅读量509

点赞数

文章标签： ACM题解报告

本文链接：https://blog.csdn.net/zhengnanlee/article/details/8518314

版权

本文探讨了一个在给定大范围数值时如何高效地解决循环周期问题的算法。通过实例分析和代码实现，展示了如何利用周期性特征优化计算效率，并详细解释了周期性的发现过程以及算法的具体应用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

为了避免百度爬虫等不必要的麻烦，还是直接贴上地址吧！

http://acm.sdut.edu.cn:8080/judge/contest/view.action?cid=5#problem/B

首先，分析题目，看到题目说n的范围最大是一亿，然后初步写出来到了50就慢得要崩溃了，所以改换思路。

#include <iostream> 
using namespace std; 
int f(int a,int b,long i)
{
	int fn;
	if(i==1||i==2)
		fn=1;
	else
		fn=(a*f(a,b,i-1)+b*f(a,b,i-2))%7;
	return(fn);
}
int main()
{
	int a,b,num[50];
	long n;
	while(1)
	{
		cin>>a>>b>>n;
		for(int i=1;i<=n;i++)
		{cout<<f(a,b,i)<<" ";}
		if(a==0&&b==0&&n==0)break; 
	}
}

利用以上代码可以分析出大概每组对应的a和b的值，发现他们是有周期性的。Ps，算到50的时候实在是太崩溃了，a=1,b=4,始终找不到最小周期，苦苦等待了半小时算完了n=50才可能发现有可能有正周期。从数论角度来讲，循环是一定会有的，因为f(n)与f(n-1)和f(n-2)存在固定的关系，他们是循环的，且最终会到达f(n-1)=f(n-2)=1这个上来。

所以，依照以前的经验，我试图寻找不同a，b与循环周期的关系如下：

a b T（最小正周期）

1 1 16

1 2 6

1 3 24

1 4 49

1 5 21

发现他们没什么必然联系，然后又崩溃了。

可是，转念一想，我既然知道了他们的周期性，我为什么不把a，b对应的49个数求出来，（ps，如果最小正周期小于49，比如是16，那么在取余的时候就直接去算就好了，没必要单列出来他们的周期是几，因为他们都包含在49里面）并存放到f[0],f[1]之内呢？（这样有个好处就是，在取余的时候出来几就是f几）

周期是49，为什么对48取余呢？因为周期是49，第49个数结果应该是第一个数的结果，而如果%49的话出来的是0，没有对应了= =。。。

代码如下：

#include <iostream> 
using namespace std; 
int main() 
{ 
    int a,b,i; 
    long n,f[50]; 
f[1]=f[2]=1; 
    while(cin>>a>>b>>n) 
    { 
if(a==0&&b==0&&n==0)break; 
else 
{ 
for(i=3;i<=48;i++) 
f[i%48]=(a*f[i-1]+b*f[i-2])%7; //把数组的每个元素对应好了存放好
            cout<<f[n%48]<<endl; //直接输出！
} 
    } 
}