题意
给定(B,X)((Ble 10^{12},Xle 60)),求有多少个(N)满足(NX)存在因子(in(N,B])
做法
令(P)为因子(in(N,B])
将(NX)表示为(PQ)。(Pin(N,B]Longrightarrow frac{NX}{Q}in(N,B]Longrightarrow Qin[1,x)And NXle QB)
为了不重复统计,在最大的满足条件的(Q)处统计,即(NX)不是(forall iin(Q,x))的倍数
考虑容斥,((-1)^{|S|}leftlfloorfrac{BQ}{lcm{S}}
ight
floor(Ssubseteq{i|iin(Q,x)}))
(|{lcm{S}|Ssubseteq{i|iin(Q,x)}And lcm{S}le BQ}|)的数量大概是(O(10^6))级别的
令(f_{i,j})为考虑([i,X))中,(lcm=j)的数量(容斥系数也算进来),转移显然