[luoguP4256]【公主の#19准备月考】

卡常大赛……

最后没开O2比开了O2还快?!

题目(洛谷)

 

首先看题,求区间gcd和lcm,我们可以将这个区间内的每个数分解质因数,gcd的话对每个质数个数取min,lcm的话取max,然而直接线段树上每个节点存该质数出现多少次的话铁定MLE。

这题的数据范围很神奇:每个值在[1,100]以内,而且题目只让求gcd和lcm(S操作可以通过求gcd求得),所以这就启发我们:将质数压起来。

我们发现:2^6=64, 2^7=128>100,所以一个区间内2的个数不超过6,而6可以用三个二进制位表示(6=4+2+0,即110);同理,3^4=81, 3^5>100,所以一个区间内3的个数不超过4,也用三个二进制位表示(4=4+0+0,即100);这样以此类推,可以得到一个区间内所有质数及其个数可以用31个二进制位表示。

而这31个二进制位,正好对应一个int的范围。所以每个节点存两个int:lcm和gcd,表示当前区间取gcd时的质数及其个数,取lcm时的质数及其个数。

然后就是普通的区间修改、区间查询了。不过还是有一些细节要注意。

…而且我被我一开始的大常数吓着了QAQ

 

发表评论