[CQOI 2015] 选数

题目大意

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

1n,  k,  l,  r1,000,000,0001 \leqslant n, \;k ,\;l, \;r \leqslant 1,000,000,000

0rl100,0000 \leqslant r - l \leqslant 100,000

题目链接

【CQOI 2015】选数 - LibreOJ 2095

题解

记答案为 f(k)f(k),由于 kk 可以除去,故可以写成:

ans=f(1)=a1=lkrk[gcd(a1,  a2,  ak)=1]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) 为:

F(x)=a1=lkrk[xgcd(a1,  a2,  ak)]=rl+1kxnF(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)=xdμ(dx)F(d)f(x) = \sum_{x | d} \mu(\frac{d}{x}) F(d)

即答案为:

ans=f(1)=d=1rμ(d)rl+1kdnans = f(1) = \sum_{d = 1}^{r} \mu(d) \lfloor \frac{r - l + 1}{kd} \rfloor ^n

注意到后面的那个分数经常会为 00,用类似莫比乌斯反演分块的方式跳过去即可。

代码

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;
}