BZOJ 3930
题意：给定$n,K,H,L$，求
这个形式和在$[1,n],[1,m]$中的$gcd$类似，我们从$N=2$开始考虑。
显然
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \left \lfloor \frac n{kd} \right \rfloor^2
$$
扩展到高维也类似，所以可以得到
$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor} \mu(d) \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n
$$
然而$\lfloor \frac Hk \rfloor$是$O(H)$级的，不能满足。
引理：
当所有数不全部相同时，$\gcd\left ( i_1, i_2, \dots, i_N \right ) \leq \max\left ( i_1, i_2, \dots, i_N \right ) - \min\left ( i_1, i_2, \dots, i_N \right )$
证明：设$d = \gcd\left ( i_1, i_2, \dots, i_N \right ), a = \min\left ( i_1, i_2, \dots, i_N \right ), b = \max\left ( i_1, i_2, \dots, i_N \right )$
显然$a = k_1d (k_1 \in \mathbb{Z}^+), b = k_2d (k_2 \in \mathbb{Z}^+, k_2 > k_1)$， 所以$b - a \geq d$，证毕。
所以$[H, L]$中的一个不全部相同的序列的$\gcd$不会超过$H - L$个，只用处理不全部相同的序列，所以可以得到
$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor - \lfloor \frac {L-1}k \rfloor} \mu(d) \left( \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n - \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )\right)+[L \leq k \leq H]
$$
注意需要加上$[L \leq k \leq H]$，因为这样就可以选$n$个$k$。
本题也可以直接杜教筛筛出$\mu(d)$的前缀和，但是我并不会……等学了杜教筛再来填坑吧。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 1000000007ll, MAXN = 100000 + 5;
LL n, k, L, H;
LL vis[MAXN], mu[MAXN], pri[MAXN], tot;
LL ksm(LL a, LL b) {
LL bs = a, ans = 1;
while (b) {
if (b & 1) ans = (ans * bs) % MO;
bs = (bs * bs) % MO;
b >>= 1;
}
return ans;
}
void clean() {
ms(vis, 0), ms(mu, 0), ms(pri, 0), tot = 0;
}
int solve() {
clean();
cin >> n >> k >> L >> H;
mu[1] = 1;
for (LL i = 2; i <= 100000; ++i) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1;
for (LL j = 1; j <= tot && pri[j] * i <= 100000; ++j) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
mu[pri[j] * i] = 0;
break ;
} else mu[pri[j] * i] = mu[i] * mu[pri[j]];
}
}
for (LL i = 2; i <= 100000; ++i) mu[i] += mu[i - 1];
LL ans = 0;
if (L <= k && k <= H) ++ans;
LL l = 1, len = H - L;
H /= k, L = (L - 1) / k;
while (l <= len && l <= H) {
LL r;
if (L / l == 0) r = H / (H / l); else r = min(H / (H / l), L / (L / l));
LL tmp = ( ksm( (H / l - L / l + MO) % MO, n ) - (H / l - L / l + MO) % MO + MO ) % MO * ( ( mu[r] - mu[l - 1] + MO ) % MO ) % MO;
ans = (ans + tmp) % MO;
l = r + 1;
}
printf("%lld\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
2 3 2 4
3 2 2 4
*/
