[BZOJ 3930][CQOI 2015] 选数

题目大意

求从 \([l, \; r]\) 中可重复地选出 \(n\) 个数,使得其 gcd 恰为 \(k\) 的方案数,答案对 \(1,000,000,007\) 取模。

\(1 \leqslant n, \;k ,\;l, \;r \leqslant 1,000,000,000\)

\(0 \leqslant r - l \leqslant 100,000\)

题目链接

BZOJ 3930

题解

记答案为 \(f(k)\),由于 \(k\) 可以除去,故可以写成: \[ ans = f(1) = \sum_{a_1 = \lfloor \frac{l}{k} \rfloor}^{\lfloor \frac{r}{k} \rfloor} \cdots [gcd(a_1, \; a_2 \cdots , \; a_k) = 1] \] 同时设 \(F(x)\) 为: \[ F(x) = \sum_{a_1 = \lfloor \frac{l}{k} \rfloor}^{\lfloor \frac{r}{k} \rfloor} \cdots [x | gcd(a_1, \; a_2 \cdots , \; a_k)] = \lfloor \frac{r - l + 1}{kx} \rfloor ^{n} \] 显然有: \[ f(x) = \sum_{x | d} \mu(\frac{d}{x}) F(d) \] 即答案为: \[ ans = f(1) = \sum_{d = 1}^{r} \mu(d) \lfloor \frac{r - l + 1}{kd} \rfloor ^n \] 注意到后面的那个分数经常会为 \(0\),用类似莫比乌斯反演分块的方式跳过去即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <climits>
#include <algorithm>
const int MOD = 1000000007;
long long pow(long long a, long long n) {
long long res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}
int mu(int n) {
int res = 1;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
res *= -1;
n /= i;
if (n % i == 0) return 0;
}
}
if (n > 1) res *= -1;
return res;
}
int main() {
long long n, k, l, r;
scanf("%lld %lld %lld %lld", &n, &k, &l, &r);
l = (l - 1) / k, r /= k;
long long ans = 0;
for (long long i = 1; i <= r; i++) {
long long temp = pow(r / i - l / i, n);
if (temp > 0) {
ans += mu(i) * temp;
ans = (ans + MOD) % MOD;
} else i = std::min(r / (r / i), l / i ? l / (l / i) : INT_MAX);
}
printf("%lld\n", ans);
return 0;
}