题意

给出n个数，问在这n个数里面，有多少组bi（1<=bi<=ai）可以使得任意两个bi不互质。

思路

想法就是枚举2~min（ai），然后去对于每个ai都去除以这些质数，然后再相乘就代表对于这个数有多少种。但是这样的想法会超时的还会算重复。

那么考虑分段计数，处理一个前缀和，代表sum[1~i]这段区间出现了多少个ai，然后对于每个因子都去枚举它的倍数，因为这段区间里面的数对于这个因子的贡献是相同的，于是可以有pow(倍数, sum[r] - sum[l-1])的贡献，这样的复杂度为nlognlogn。但是还有一个重要的问题，就是会算重复，例如当因子为2和4和6的情况。

这个时候就要用到莫比乌斯反演。

我觉得莫比乌斯反演就是用在有约数关系时候的容斥原理。处理出来的表的时间复杂度是O（n）的。

比较常用的意义：

$ F(n) $ 表示约数为n的组数有多少。

$ f(n) $ 表示最大公约数为n的组数有多少。

\[F(n)=\sum_{d|n}f(d)
\]

d|n表示d为n的因子。

\[f(n)=\sum_{n|d}\mu(i)F(\frac{d}{i})
\]

一般我们求 $ f(1) $ 就是求gcd为1即互质的情况下的组数，这道题求的是不互质，即为 $ f(2) + f(3) + f(4) … + f(min(a)) $ 这个情况下要把 $ \mu(d) $ 乘个-1。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

typedef long long LL;

int vis[N], mu[N], prime[N], sum[N*2];

void mobius(int n) {

    mu[1] = 1;

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

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

            mu[j] -= mu[i];

        }

    }

    memset(vis, 0, sizeof(vis));

    mu[1] = 1; int cnt = 0;

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

        if(!vis[i]) {

            prime[cnt++] = i;

            mu[i] = -1;

        }

        for(int j = 0; j < cnt && i * prime[j] <= n; j++) {

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

            if(i % prime[j]) mu[i*prime[j]] = -mu[i];

            else { mu[i*prime[j]] = 0; break; }

        }

    }

}

LL f_pow(LL a, int b) {

    LL ans = 1;

    while(b) {

        if(b & 1) ans = ans * a % MOD;

        a = a * a % MOD;

        b >>= 1;

    } return ans % MOD;

}

int main() {

    int t; scanf("%d", &t);

    mobius(100000);

    for(int cas = 1; cas <= t; cas++) {

        int n; scanf("%d", &n);

        memset(sum, 0, sizeof(sum));

        int mi = N, ma = 0;

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

            int a; scanf("%d", &a);

            sum[a]++;

            if(a < mi) mi = a;

            if(a > ma) ma = a;

        }

        for(int i = 1; i < 2 * N; i++) sum[i] += sum[i-1];

        LL ans = 0;

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

            LL tmp = 1, k = 1;

            for(int j = i; j <= ma; j += i, k++)

                tmp = tmp * f_pow(k, sum[j+i-1] - sum[j-1]) % MOD; // 在j到j+i-1这段区间里面整除i的有k个数

            ans = (ans - tmp * mu[i] + MOD) % MOD;

        }

        printf("Case #%d: %lld\n", cas, (ans + MOD) % MOD);

    }

    return 0;

}

巴特西

HDU 6053：TrickGCD（莫比乌斯反演）

题意

思路

最新文章

热门文章