题目传送门(BZOJ)

杜教筛

>原文链接<

题解 :

题意即求

$$\sum\limits_{a_1=L}^{R}\sum\limits_{b_1=L}^{R}\cdots\sum\limits_{a_N=L}^{R}[\gcd(a_1, a_2, \cdots, a_N)=d]$$

$$\sum\limits_{a_1=\lfloor\frac{L}{d}\rfloor}^{\lfloor\frac{R}{d}\rfloor}\sum\limits_{b_1=\lfloor\frac{L}{d}\rfloor}^{\lfloor\frac{R}{d}\rfloor}\cdots\sum\limits_{a_N=\lfloor\frac{L}{d}\rfloor}^{\lfloor\frac{R}{d}\rfloor}[\gcd(a_1, a_2, \cdots, a_N)=d]$$

反演

$$\therefore \sum\limits_{a_1=\lfloor\frac{L}{d}\rfloor}^{\lfloor\frac{R}{d}\rfloor}\sum\limits_{b_1=\lfloor\frac{L}{d}\rfloor}^{\lfloor\frac{R}{d}\rfloor}\cdots\sum\limits_{a_N=\lfloor\frac{L}{d}\rfloor}^{\lfloor\frac{R}{d}\rfloor}\sum\limits_{p|\gcd(a_1,a_2,\cdots a_N)}\mu(p)$$

枚举$p$

$$\sum\limits_{p=1}^{\lfloor\frac{R}{d}\rfloor}\mu(p)(\lfloor\frac{R}{dp}\rfloor-\lfloor\frac{L-1}{dp}\rfloor)^n$$

对于后面部分,分块求和

对于前面部分,杜教筛求$S_\mu$

本题解决完毕。

#include <map>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 10000000;const int p = 1e9+7;int s[N], mu[N], pr[N/10], tot;bool vis[N];map<int, int>f;#define ll long longll qp(ll x, int y) { if(!y) return 1; ll tmp = qp(x, y>>1); return y&1?tmp*tmp%p*x%p:tmp*tmp%p;}ll query(ll x) { if(x < N) return s[x]; if(f.find(x) != f.end()) return f[x]; ll i, lst, ans = 1; for(i = 2; i <= x; i = lst+1) { lst = x/(x/i); ans -= (lst-i+1)*query(x/i); ans %= p; } return f[x] = ans;}void init() { mu[1] = s[1] = 1; for(int i = 2; i < N; i ++ ) { if(!vis[i]) mu[i] = -1, pr[++tot] = i; for(int j = 1; j <= tot && i*pr[j] < N; j ++ ) { vis[i*pr[j]] = 1; if(i%pr[j] == 0) break; mu[i*pr[j]] = -mu[i]; } s[i] = (s[i-1]+mu[i])%p; }}int main() { init(); int n, d, l, r; scanf("%d%d%d%d", &n, &d, &l, &r); ll ans = 0; int lst; l = (l-1)/d, r = r/d; for(int i = 1; i <= r; i = lst+1) { lst = r/(r/i); ans += (query(lst)-query(i-1))%p*qp(r/i-l/i, n)%p; ans %= p; } printf("%lld\n", ans); getchar(), getchar();}