Day12

【质数生成器】
题意:询问区间[m,n]里的质数,1<=m<=n<=10^9,n-m<=1000000。
显然线筛过不了1e9的数据,只能对[m,n]区间求质数。
一个数n如果是合数,那么必定会被sqrt(n)中的质数整除,考虑普通筛(233)。对于[m,n]中的数,只需枚举每个质数,将其在这个区间中的倍数筛去即可。
正确性:线筛只要将sqrt(n)中的质数筛出,大概是1e5左右,明显不会超时。[m,n]区间的普通筛是用质数去筛,比用每个数筛的时间大大减少。
【魔法树】
题意:一棵树,每个点有一种属性。一条路径上的魔法值是这样计算的:在起点的时候,魔法值为 1,每经过一条边,假设这条边拥有的魔法属性是 ci,如果这是奇数次经过带有 ci 魔法属性的边,则将魔法值乘上 ci 对应的魔法系数,否则将魔法值除以 ci 对应的魔法系数。
简化题目,即如果奇数次经过ci的点,那么答案就乘上di,否则这个ci对答案没用贡献。
考虑用二进制来表示每种属性的贡献,对于询问的两个点,只需以任意的点为树根,求出每个点的二进制数,在询问使^即可。
【hill】
题意:给出一座山,求一个最低的点能够看到所有地方。
简单的三分题。