没做过容斥题,因此即使是绿题也很难想
首先看数据范围 \(n \leq 25\) 可以想到这题复杂度应该是指数级别的
我们先对答案差分,\(ans = solve(r) - solve(l-1)\),因此我们只需要计算\(solve(x)\)即可
可以表示出的取值一定能被某个 \(x_i\) 的倍数 \(y\) 表示
因此一个\(x_i\)倍数的\(y\)一定和某个\(x\)形成一一对应的关系
我们可以通过二分找到满足答案\(=x\)的\(Y\),然后问题就变成了统计在\([1,Y]\)内有多少个数是任一\(x_i\)的倍数
直接考虑容斥即可
最终复杂度\(O(\log l + 2^n)\)