FJNUOJ1158（莫比乌斯反演）

题目：给定n个数字a1...an。有m个询问，格式为L R X Y，意为求aL到aR之间与x的最大公因数为y的个数。

　　　数据组数T<=20

　　　1<=n,m<=1e5

　　　1<=ai<=1e5

　　　1<=L,R<=n;1<=X,Y<=1e5

分析：

　　考虑预处理出1~1e5所有数字的因子

　　　然后就可以知道每个因子在1~n这n个位置的分布情况

　　　对于一个询问(l,r,x,y)

　　　就相当于求[l,r]之间公因数为y，[l,r]之间公因数为2y，[l,r]之间公因数为3y……等等这些做容斥，很容易就看出这满足经典的莫比乌斯反演

　　　具体的F(n)表示[l,r]之间和x共有因数y的数字的个数，f(n)表示[l,r]之间和x的最大公约数位y的数字的个数

　　　那么f(n)=Σμ(d/n)F(d)

　　　那么F(d)怎么求呢，F(d)其实就是因数d在[l,r]中出现了几个，直接二分就行了

　　　复杂度不好估计，但不会超过O(n根号n)

巴特西