数学 Ⅱ

信息里的数学 ~

数学技巧 \(\&\) 数列

前言：这其中可以观察一个数列的性质，其中潜在的一些关键部分，找到这些突破口轻松解题。

\(Problem \ 1\)

\(\color{black}{\rightarrow Link}\)

用到了一个很巧妙的点。首先观察数据范围。

\(n \leq 10^5,a_i \leq 10^6\)

然而即便是 \(1\times fib\) 的第 \(31\) 项也超出了 \(10^6\)，因此可以对 \(10^6\) 这个值域开始处理。

首先 \(\{ a \}\) 的 \([31,\infty]\) 项不需要管，直接最后把贡献加上去就好了。

然后对于每一个倍数 \(base\in \{1,10^6\}\) 暴力枚举就好了，其中 \(\{fib\}\) 直接预处理就好了。

代码短小。

for(int b=1;b<=1e6;++b){
		res=0;
		for(int i=1;i<=31;++i)
			if(a[i]!=fib[i]*b) res++;
		ans=min(ans,res);
	}