【bzoj3136】brunhilda

Source and Judge

Baltic2013
bzoj3136

Record

2h

Analysis

请先思考后再展开

首先有个结论,就是每个数搞完的次数是不递减的
因为首先每个操作相当于按p分组,然后每组变为第一个,
那么一个数只要小,以后都是小的,相对关系不会变
$f(i)=f(j)+1$
显然j是某个p的倍数

那么每个j,要向后最多,则找j的约数中在P里出现,最大的那个,以影响最大的范围
这个可以线性筛出minp来实现递推

方法一,枚举每个j,用单调队列维护影响范围
方法二,枚举每个i,观察j+vj<=i的i是递增的,则决策点递增,可以维护指针扫过去

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b76f.html
转载请注明出处,谢谢!