选数

题目链接：luogu P3172

题目大意

你可以在 [L,H] 区间中选 N 个数（可以相同），然后要它们的 gcd 恰好为 K，然后问有多少种选的方案。

思路

首先你考虑你可以枚举 K K K 的倍数作为 gcd ⁡ \gcd gcd，然后容斥得到 K K K 为 gcd ⁡ \gcd gcd 的。
然后假设你看 x x x 的时候你就会发现就是要找 [ L , H ] [L,H] [L,H] 区间有多少个数是 x x x 的倍数。

那我们就直接可以用前缀和。
所以右边的那个就是 ⌊ H K ⌋ \left\lfloor\dfrac{H}{K}\right\rfloor ⌊KH​⌋，左边的就是 ⌊ L − 1 K ⌋ \left\lfloor\dfrac{L-1}{K}\right\rfloor ⌊KL−1​⌋。

然后由于 H − L + 1 H-L+1 H−L+1 是 1 0 5 10^5 105 级别的，所以它们除了所有数都相同，最大的 gcd ⁡ \gcd gcd 就是 1 0 5 10^5 105 级别，那我们就可以 O ( n log ⁡ n ) O(n\log n) O(nlogn) 容斥每个减去它的倍数的结果得到。
而且要注意一些就是因为不能全部相同，所以如果你选出来区间中有 x x x 个它的倍数，未容斥的方案数是 x N − x x^N-x xN−x。

然后记得最后的答案如果区间有 1 1 1 在里面要加一。

代码

#include<cstdio>
#define ll long long
#define mo 1000000007

using namespace std;

ll n, k, l, h, lim;
ll f[100001];

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo;
		y >>= 1;
	}
	return re;
}

ll Ask(ll g) {
	return (ksm(h / g - l / g, n) - (h / g - l / g) + mo) % mo;
}

int main() {
	scanf("%lld %lld %lld %lld", &n, &k, &l, &h);
	
	l = (l - 1) / k; h /= k;//直接变成要 gcd=1
	f[h - l + 1] = Ask(h - l + 1);
	for (ll i = h - l; i >= 1; i--) {//容斥
		f[i] = Ask(i);
		for (ll j = i + i; j <= h - l + 1; j += i)
			f[i] = (f[i] - f[j] + mo) % mo;
	}
	
	if (l < 1) f[1] = (f[1] + 1) % mo;
	printf("%lld\n", f[1]);
	
	return 0;
}