bzoj4176

莫比乌斯反演

根据约数和个数公式

$ans = \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{x|i}\sum_{y|j}{[gcd(i, j)==1]}$

交换枚举顺序

$ans = \sum_{x=1}^{n}\sum_{y=1}^{n}{[\frac{n}{x}][\frac{n}{y}]*[gcd(x, y)==1]}$

$=\sum_{x=1}^{n}\sum_{y=1}^{n}{[\frac{n}{x}][\frac{n}{y}]\sum_{d|x,y}{\mu(d)}}$

再交换枚举顺序

$=\sum_{d=1}^{n}{\mu(d)\sum_{i=1}^{\frac{n}{d}}{\frac{n}{di}}\sum_{j=1}^{\frac{n}{d}}{\frac{n}{dj}}}$

设$f(n)=\sum_{i=1}^{n}{\frac{n}{i}}$

那么$=\sum_{d=1}^{n}{\mu(d)f(\frac{n}{d})^{2}}$

这就可以分块求了，$\mu$用杜教筛求，$f$用二次分块

反演就是不断交换求和顺序或者改变枚举变量

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

typedef long long ll;

const int N = 1e7 + , P = 1e9 + ;

int n;

ll ans;

int p[N], mark[N], mu[N];

map<int, ll> sum_1;

void ini() {

    mu[] = ;

    for(int i = ; i < N; ++i) {

        if(!mark[i]) {

            p[++p[]] = i;

            mu[i] = -;

        }

        for(int j = ; j <= p[] && i * p[j] < N; ++j) {

            mark[i * p[j]] = ;

            if(i % p[j] == ) {

                mu[i * p[j]] = ;

                break;

            }

            mu[i * p[j]] = -mu[i];

        }

    }

    for(int i = ; i < N; ++i) {

        mu[i] += mu[i - ];

    }

}

ll dj_m(int n) {

    if(n < N) {

        return mu[n];

    }

    if(sum_1.find(n) != sum_1.end()) {

        return sum_1[n];

    }

    ll ret = ;

    for(int i = , j = ; i <= n; i = j + ) {

        j = n / (n / i);

        ret = (ret - (ll)(j - i + ) * dj_m(n / i) % P + P) % P;

    }

    return sum_1[n] = ret;

}

ll calc(int n) {

    ll ret = ;

    for(int i = , j = ; i <= n; i = j + ) {

        j = n / (n / i);

        ret = (ret + (ll)(n / i) * (j - i + ) % P) % P;

    }

    return ret;

}

int main() {

    ini();

    scanf("%d", &n);

    for(int i = , j = ; i <= n; i = j + ) {

        j = n / (n / i);

        ll a = ((dj_m(j) - dj_m(i - )) % P + P) % P, b = calc(n / i);

        ans = (ans + a * b % P * b % P) % P;

    }

    printf("%lld\n", ans);

    return ;

}

巴特西

bzoj4176

最新文章

热门文章