CF915G Coprime Arrays 莫比乌斯反演、差分、前缀和

差分是真心人类智慧……完全不会

这么经典的式子肯定考虑莫比乌斯反演，不难得到\(b_k = \sum\limits_{i=1}^k \mu(i) \lfloor\frac{k}{i} \rfloor^n\)

直接做是\(O(n\sqrt{n})\)的不够优秀，但是我们需要求的是\(b_1\)到\(b_K\)而不是单独的一个\(b\)，这是最重要的一个性质。

考虑每一个数\(p\)对\(b_1\)到\(b_k\)的贡献。因为\(\mu(p)\)不变，所以对于\(\forall k \in Z_+ ,\)数\(p\)对\(b_{kp}\)到\(b_{(k+1)p-1}\)的贡献是一致的，都是\(\mu(p) k^n\)。既然对于一段区间的贡献相同，那就差分一下，最后前缀和统计答案即可。

总复杂度为预处理\(n\)次方的\(O(klogn)\)加上差分时的\(O(klogk)\)。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<cctype>

#include<algorithm>

#include<cstring>

#include<iomanip>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<vector>

#include<cmath>

#include<random>

#include<cassert>

//This code is written by Itst

using namespace std;

inline int read(){

    int a = 0;

    char c = getchar();

    bool f = 0;

    while(!isdigit(c) && c != EOF){

        if(c == '-')

            f = 1;

        c = getchar();

    }

    if(c == EOF)

        exit(0);

    while(isdigit(c)){

        a = a * 10 + c - 48;

        c = getchar();

    }

    return f ? -a : a;

}

#define ll long long

const int MAXN = 2e6 + 3 , MOD = 1e9 + 7;

int powx[MAXN] , prime[MAXN] , mu[MAXN] , cf[MAXN];

bool nprime[MAXN];

int cnt , N , K;

inline int poww(ll a , int b){

    int times = 1;

    while(b){

        if(b & 1)

            times = times * a % MOD;

        a = a * a % MOD;

        b >>= 1;

    }

    return times;

}

void init(){

    for(int i = 1 ; i <= K ; ++i)

        powx[i] = poww(i , N);

    mu[1] = 1;

    for(int i = 2 ; i <= K ; ++i){

        if(!nprime[i]){

            prime[++cnt] = i;

            mu[i] = -1;

        }

        for(int j = 1 ; prime[j] * i <= K ; ++j){

            nprime[prime[j] * i] = 1;

            if(i % prime[j] == 0)

                break;

            mu[prime[j] * i] = mu[i] * -1;

        }

    }

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("in","r",stdin);

    //freopen("out","w",stdout);

#endif

    N = read();

    K = read();

    init();

    for(int i = 1 ; i <= K ; ++i)

        for(int j = 1 ; j * i <= K ; ++j)

            (cf[j * i] += mu[i] * (powx[j] - powx[j - 1] + MOD) % MOD) %= MOD;

    int ans = 0;

    for(int i = 1 ; i <= K ; ++i){

        cf[i] = (0ll + MOD + cf[i] + cf[i - 1]) % MOD;

        ans = (ans + (cf[i] ^ i)) % MOD;

    }

    cout << ans;

    return 0;

}

巴特西

CF915G Coprime Arrays 莫比乌斯反演、差分、前缀和

最新文章

热门文章