BZOJ 3930: [CQOI2015]选数 – [莫比乌斯反演/杜教筛]


题目传送门(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 
#include 
#include 
#include 
using namespace std;
const int N = 10000000;
const int p = 1e9+7;
int s[N], mu[N], pr[N/10], tot;
bool vis[N];
mapf;
#define ll long long
ll 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();
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注