huanghai
/
python
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'main'
${ noResults }
python/TangDou/Topic/莫比乌斯函数.md

14 KiB
Raw Permalink Blame History Escape

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

莫比乌斯函数

【数论】为什么莫比乌斯函数长这样？这样理解最自然！

【数论】莫比乌斯函数/莫比乌斯反演

https://blog.csdn.net/qq_49593247/article/details/120394226

一、莫比乌斯函数

先明确一点，莫比乌斯函数并不是什么很高大上的东西，它其实只是一个由容斥系数所构成的函数。

视频讲解：两分钟学会墨比乌斯函数

1. 定义

莫比乌斯函数是个分段函数,它的意思:

  • ① 当n=1时,莫比乌斯函数值为1
  • ② 当n为可以分解为许多素数并且这些质因子的次数都是1时,莫比乌斯值就是-1的 质数因子个数的幂次方
  • ③ 除了这些情况剩余的情况莫比乌斯函数值都是0

前五十个数的莫比乌斯值.

打印前20个数字的莫比乌斯函数值

函数值 1 -1 -1  0 -1  1 -1  0  0  1 -1  0 -1  1  1  0 -1  0 -1  0 
数 字: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20

2. 用途

我们举例一道经典的应用题，求1到N中与a互质的数的个数：根据容斥原理，设S_i为1到N中和a有公因子i的数的个数，答案为N−S_2-S_3-S_5-S_7...+S_{2,3}+S_{3,5}+S_{2,5}...,可以发现，其答案为\large \displaystyle \sum_{i=1}^{N}\mu(i)*S_i。

注：在使用容斥原理解决计数问题时，莫比乌斯函数的值就是每一项的系数，要么是1，要么是-1。这是因为莫比乌斯函数在容斥原理中的作用就是用来表示每个子集合的权重，从而在计算中起到排除重复计数的作用。

3. 求单个数字的莫比乌斯函数值

// 单个数的莫比乌斯函数
int getmob(int x) {
    int sum = 0;
    for (int i = 2; i <= x / i; i++) { // 从2开始，一直到 sqrt(x),枚举所有可能存的小因子
        int cnt = 0;
        if (x % i == 0) {                     // 如果x可以整除i
            while (x % i == 0) cnt++, x /= i; // 计数，并且不断除掉这个i因子
            if (cnt > 1) return 0;            // 如果某个因子，存在两个及以上个，则返回0
            sum++;                            // 记录因子个数
        }
    }
    if (x != 1) sum++;         // 如果还存在另一个大因子，那么因子个数+1
    return (sum & 1) ? -1 : 1; // 奇数个因子，返回-1,否则返回1
}

4.欧拉筛扩展求莫比乌斯函数

视频讲解

// 筛法求莫比乌斯函数(枚举约数)
int mu[N], sum[N]; // sum[N]:梅滕斯函数,也就是莫比乌斯函数的前缀和
int primes[N], cnt;
bool st[N];
void get_mobius(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0) {
                mu[t] = 0;
                break;
            }
            mu[t] = -mu[i];
        }
    }
    // 维护u(x)前缀和:梅滕斯函数
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i];
}

二、题单

SP4168 SQFREE - Square-free integers

题意 在数论中，如果一个整数不能被任何一个整数（这个整数不是1）的平方整除，我们就称它是一个Square−freeinteger（无平方数因数的数）。你得数一数!

求出1 \sim n 中无平方因子数的个数。

题解

先来求一下 平方数因数 的数有多少个：

在[1, n] 中，有多少个数是x^2的倍数? 显然是⌊\frac{n}{x^2}⌋个。

那 ⌊\frac{n}{x^2}⌋ 就是答案了吗？当然不是，有大量的数被重复计算了。

例如 36，它等于2^2\times 3^2 ，在计算 2 和 3 的时候它会被重复计算。

怎么办呢？

利用容斥思想，1到n以内有平方因数的数有\large \frac{n}{2^2}+\frac{n}{3^2}+\frac{n}{5^2}-\frac{n}{6^2}...。

注： ① 为什么没有4^2,8^2呢？这是因为4^2=4 \times 2^2,8^2=16\times 2^2,在计算2^2的个数时，已经计算过了，同理，合数都可以拆分成质数的乘积，我们只要计算质数的平方就可以了。 ② 但是 6^2=2^2\times 3^2这样的数字比较特殊，它会被在计算2^2时计算一遍，在计算3^2时又计算了一遍，计算重复了，需要再扣除掉\frac{n}{6^2}个,这里可以看出来符合容斥原理。

Q:即然这是容斥原理，和莫比乌斯函数有什么关系？ 答：从现实意义上去看看：

  • 2,3,5都是一个质数因子，它的系数是1
  • 4=2^2,按莫比乌斯函数的说法，系数为0,无贡献
  • 6 = 2 \times 3,有两个质数因子，系数是-1

这不就是莫比乌斯函数的定义吗？

可知以上式子 \displaystyle =-\sum_{2 \leq d \leq \sqrt{n}} \mu(d)*⌊\frac{n}{d^2}⌋

注：为什么只枚举到\sqrt{n},而不是到n呢？这是因为：d>\sqrt{n}时，⌊\frac{n}{d^2}⌋恒等于0，再继续也是无贡献，只需要枚举到\sqrt{n}即可。

所以无平方因数的数就是 求补集=\displaystyle n-(-\sum_{2 \leq d \leq \sqrt{n}} \mu(d)*⌊\frac{n}{d^2}⌋)=n+\sum_{2 \leq d \leq \sqrt{n}} \mu(d)*⌊\frac{n}{d^2}⌋个。

变形合并,d=1,\mu(d)=1(莫比乌斯的分段函数求得) \mu(d)*⌊\frac{n}{d^2}⌋=\mu(1)*(n/1^2)=1*n=n

此时可以发现这个式子，第一项也可以合并进来，合并成

\displaystyle \sum_{1 \leq d \leq \sqrt{n}} \mu(d)*⌊\frac{n}{d^2}⌋

⌊\frac{n}{d^2}⌋是整除分块的基本形式，用整除分块优化，区间的数值都是一样的，但每项的符号有加有减，一个个算太慢了，可以给μ(x)预处理出前缀和，这样直接用O(1)时间计算前缀和，再乘上整除分块的数值就行了~

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int M = 110;      // 询问次数
const int N = 10000010; // 莫比乌斯函数值的极限数据上限,sqrt(1e14)=1e7
int n, sqrtN;           // T次询问，每次都是1~n,sqrtN=sqrt(max(n)),真实上限
int q[M];               // T次询问，用q数组记录下来

// 筛法求莫比乌斯函数(枚举约数)
int mu[N], sum[N]; // sum[N]:梅滕斯函数,也就是莫比乌斯函数的前缀和
int primes[N], cnt;
bool st[N];
void get_mobius(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0) {
                mu[t] = 0;
                break;
            }
            mu[t] = -mu[i];
        }
    }
    // 维护u(x)前缀和:梅滕斯函数
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i];
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("SQP4168.in", "r", stdin);
#endif
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> q[i];
        n = max(n, q[i]); // 找到最大的n,这样可以避免重复计算
    }
    sqrtN = sqrt(n); // 最大的n，只需要枚举到sqrt(n)即可
    // 对有效范围内的数字求莫比乌斯函数
    get_mobius(sqrtN); // 线性求莫比乌斯函数, 前缀和

    for (int i = 1; i <= T; i++) {              // 离线处理，对于每个询问进行回答
        n = q[i];                               // 第i次的n值
        int ans = 0;                            // 初始化返回结果
        for (int l = 1, r; l <= n; l = r + 1) { // 整除分块
            if (n / (l * l) == 0) break;
            // n / (l * l): 分块的左边界是l,值是n/(l*l),如果n<(l*l)时，l再长大也没用，也都是0
            // n/(l*l):整除分块中整个分块内的个数值，从n/(l*l)~n/(r*r)是同一个值
            r = sqrt(n / (n / (l * l)));                // 求出右边界r
            ans += n / (l * l) * (sum[r] - sum[l - 1]); // 利用莫比乌斯函数值前缀和求块的贡献
        }
        cout << ans << endl;
    }
}

P4318 完全平方数

题意 小X自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。

这天是小X的生日，小W想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第K个数送给了小X。小X很开心地收下了。

然而现在小W却记不起送给小X的是哪个数了。你能帮他一下吗？

解法 设f(n)表示在1到n中小X不讨厌的数的数量。显然f(n)是 单调递增 的，所以我们可以二分答案。

注: 与上一题的区别在于上一题明确给出了最大值n,也就是右边界的范围，本题没有告诉我们范围，需要我们自己找到右边界。随着右边界越来越大，肯定符合条件的数字个数也会越来越多，也就是上面说到的单调性。我们可以用二分来假设一个右边界，然后不断的收缩区间来找到准备的右边界:在上道题的基础上加上二分，判断1到mid是否有K个无平方因子的数，以此改变左右边界即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 100010;

// 筛法求莫比乌斯函数(枚举约数)
int mu[N];
int primes[N], cnt;
bool st[N];
void get_mobius(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0) {
                mu[t] = 0;
                break;
            }
            mu[t] = -mu[i];
        }
    }
}
int check(int mid, int k) {
    int res = 0;
    for (int i = 1; i * i <= mid; i++) // 枚举范围内每个平方数
        res += mu[i] * (mid / i / i);
    return res >= k;
}

signed main() {
    // 获取莫比乌斯函数值
    get_mobius(N - 1);

    int T, k;
    cin >> T; // T组测试数据
    while (T--) {
        cin >> k; // 第k个数
        int l = 1, r = 2e9;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid, k))
                r = mid;
            else
                l = mid + 1;
        }
        cout << r << endl;
    }
}

例题:数字染色

题目意思:

给一个数组,在其中选数,看可以最多选出多少个gcd(最大公约数)>1的集合.

要求gcd>1,那我们就把他们的约数全部求出来,记录在一个si数组里(下标为这个约数的值,里面储存它作为约数被数组中的数用了多少次).然后我们遍历这个si数组,把每个约数可能组成的约数次数算出来,例如假设2作为约数被数组中的数被总共用了2次,那么它所有可以组成的约数就是1,2,4,也就是2^2-1种组合.而当我们选择计算了2的所有可以组成的公约数,3所有的可以组成的公约数,那么当我们计算6时,就会发现6已经被2和3计算过了,很好,容斥定理,用莫比乌斯函数作为系数求(2^n-1)的和,但是还有一个问题,当选择的是奇数个质数来计算个数时,应该加上,而莫比乌斯函数值为-1,而选偶数个时应该减去,所以在求莫比乌斯值时我们可以取个反,最终我们要求的式子就是:

#include<iostream>
#define ll long long
using namespace std;
ll a[200005],vis[200005],p[200005],mo[200005];
ll si[200005];
const ll mod=1e9+7;
void init()
{
    ll tot=0,k;
    mo[1]=1;
    for(int i=2;i<=200005;i++)
    {
        if(vis[i]==0)
        {
            p[++tot]=i;
            mo[i]=1;
        }
        for(int j=1;j<=tot&&(k=i*p[j])<=200005;j++)
        {
            vis[k]=1;
            if(i%p[j]==0)
            {
                mo[k]=0;
                break;
            }
            else mo[k]=-mo[i];
        }
    }
}
ll qpow(ll pp,ll x)
{
    ll ans=1;
    while(x)
    {
        if(x&1)ans=ans%mod*pp%mod;
        pp=pp*pp%mod;
        x>>=1;
    }
    return ans;
}
int main()
{
    ll n,ans=0;
    init();
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        for(int j=1;j*j<=a[i];j++)
        {
            if(j*j==a[i])
                si[j]++;
            else if(a[i]%j==0)
            {
                si[j]++;
                si[a[i]/j]++;
            }
        }
    }
    for(int i=2;i<=200005;i++)
    {   
        ans+=(mo[i]*(qpow(2,si[i])-1)%mod)%mod;       
    }
    printf("%lld",(ans%mod+mod)%mod);
    return 0;
}

https://blog.csdn.net/qq_49593247/article/details/120394226

https://www.cnblogs.com/letlifestop/p/10262757.html

// https://blog.csdn.net/qq_42887171/article/details/95237740