bzoj3136: [Baltic2013]brunhilda

题目链接

bzoj3136

题解

\(f[i]\)表示题中所求,通过思考可以发现\(f[i]\)一定是单调不降的,所以我们要找到一些可以对\(f[i]\)产生贡献的\(j\),可以发现当\(j\)满足\(i+1\leq j\leq i+num[x]-1\)的时候,可以对\(f[i]\)产生\(1\)的贡献,然后使用队列优化一下可以达到\(O(n)\)的复杂度.

\(num[x]\)表示的是这个数\(x\)最大能被给定的质数表中的数字整除的数字.(即数\(x\)能被整除的最大的质数.)(在所有的给定的质数中)


By:Wahacer

2018.3.6

18:37

发表评论

电子邮件地址不会被公开。 必填项已用*标注