莫比乌斯反演

莫比乌斯反演

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

莫比乌斯函数

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

  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竞赛数论的个人笔记

全部评论

相关推荐

秒拒也太伤人心了
码农索隆:非得字节嘛
投递字节跳动等公司10个岗位
点赞 评论 收藏
分享
不会取名字的牛油:包大厂的,项目最好维护一个git仓库然后把地址贴上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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