我们知道，从区间[L,H]（L和H为整数）中选取N个整数，总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的N个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小z会告诉你一个整数K，你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大，你只需要输出其除以1000000007的余数即可。
输入一行，包含4个空格分开的正整数，依次为N，K，L和H。
输出一个整数，为所求方案数。
2 2 2 4
3
样例解释
所有可能的选择方案：(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)
其中最大公约数等于2的只有3组：(2, 2), (2, 4), (4, 2)
对于100%的数据，1<=N,K<=10^9，1<=L<=H<=10^9，H-L<=10^5
最初的想法是莫比乌斯反演，但写了一半发现好麻烦，还要杜教筛之类的。。。 于是放弃！上普通容斥！
我们发现 \(H-L \leq 10^5\) ，那对于这个范围内，任意两不同的数的gcd \(\leq 10^5\) （这个应该还是挺显然的。这两个数的差一定是它们gcd的倍数）
我们先把L与H处理一下，都除以K，将问题转变为求某一区间\([l,r]\)内选N个数gcd为1的方案数。 设 \(f[i]\) 表示该区间内选N个数（这N个数不全相同），gcd为i的方案数 （一会儿我会解释为什么要N个数不全相同） 那么 $f[i]=[r/i-l/i]^n - [r/i-l/i] - \sum\limits_{i|j} f[j] $ 其中减去的 $[r/i-l/i] $ 便是N个数都相同的情况。 最后需要特判一下是否N个数可以都取K，若可以答案为\(f[1]+1\)，否则为\(f[1]\)
好，现在解释一下为什么\(f[i]\)中选的N个数不全相同（想了好久才明白qwq） 一开始我想的是，计算\(f[i]\)时不需减掉 \([r/i-l/i]\)，因为所有 \(f[i]\) 都带上 \((i,i,i,i,…)\) ，在 $ - \sum\limits_{i|j} f[j]$ 时肯定会被消掉。 可是，对于区间\([l,r]\)中的任意一个数x， \((x,x,x,x,x…)\) 的gcd为x，可能是超过\(10^5\)的。 而我们的\(f[i]\)最多只到\(10^5\)，所以如果\(f[i]\)包括N个数都相同的情况的话，会有一些 \((x,x,x,x,…)\) 没有被减掉 而我们又知道，若N个数都相同且gcd为K，那只有这N个数都为K这一种情况。对这种情况特判一下就可以了。
莫比乌斯反演与普通容斥的异同： 对于这道题的条件，两者都可以由 \(F(i)=f(i)+f(2i)+f(3i)+…\) 的式子写成，其中\(F(i)\)极其好求，而\(f(i)\)是我们需要的答案。 莫比乌斯反演是只通过\(F()\)求\(f()\)，用到莫比乌斯函数 而普通容斥的做法就是递推，通过\(F()\)及\(f()\) 求\(f()\) 一般来说莫比乌斯反演时间复杂度可以优化到\(O(\sqrt{n})\)，比普通容斥快；而普通容斥比莫比乌斯反演好写许多。 所以要具体问题具体分析，再决定用哪种做法。
转载于:https://www.cnblogs.com/lindalee/p/8660475.html
