莫比乌斯反演

莫比乌斯反演

图片说明图片说明 是定义在非负整数集合上的两个函数,并且满足条件 图片说明 。那么,我们得到结论:
图片说明
证:图片说明

莫比乌斯函数

在上面的公式中有一个莫比乌斯函数 图片说明 ,它的定义如下:

  1. 图片说明 ,那么 图片说明
  2. 图片说明 均为互异素数,那么图片说明
  3. 其他情况下图片说明

性质

对于图片说明 函数,它有如下的常见性质:

  1. 图片说明 表示 n 的质因子个数, 对任意正整数 n 有:图片说明

证:图片说明

  1. 对任意正整数 n 有:图片说明

证:图片说明

用线性筛选求莫比乌斯反演函数的代码:

int init(int n) {
    int tot = 0;
    for(int i = 1; i <= n; ++ i) vis[i] = 0;
    for(long long i = 2; i <= n; ++ i) {
        if (!vis[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1; i * prime[j] <= n; ++ j) {
            vis[i*prime[j]] = 1;
            if (i % prime[j] == 0) break;
            else mu[i*prime[j]] = -mu[i];
        }
    }
    return tot;
}
数学 文章被收录于专栏

关于acm竞赛数论的个人笔记

全部评论

相关推荐

昨天 14:04
东北大学 C++
既然这样,为什么不点击就送呢
牛马88号:因为你合适。但有很多笔试就挂了、通过了再排序的
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务