题解:
老早之前看的并没有写题解。。
t1:
我刚开始想的是线段树来维护。。
看了题解发现直接二分就行了
很容易发现因数只会有30个
那么我们就统计每一种因数在这段区间的个数
然后开个vector记录这种因数的位置 二分一下就好了
nlog^2
t2:
t3:
我觉得这道题出的还是不错的
首先考虑一下如果我们知道它的结构怎么统计方案数
会发现就是f(x)=f(son1)*f(son 2)*C(son1+son2,son1)
然后我们考虑怎么去构造方案
首先我们考虑一下暴力dfs
那么f(son1)一定就是它的约数
而继续下去也一定都是它的约数,这样我们就可以考虑记忆化搜索了
那么记录的状态是什么呢? 我们去记录,方案数为x,最少要用几个点
这样我们的问题就变成了 要确定f(son2)*C(son1+son2,son1)>=k 其中son1>=y
那么我们可以考虑预处理出当son1至少要x个点时,要表示出k,至少需要几个点
这样我们询问是o(1)的 考虑一下怎么维护