51Nod 1240 莫比乌斯函数 ——————莫比乌斯函数

骑猪看日落 2022-05-15 04:27 237阅读 0赞

**1240 莫比乌斯函数**

基准时间限制：1 秒  
空间限制：131072 KB  
分值: 0  
难度：基础题

莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。（据说，高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数）。

具体定义如下：  
如果一个数包含平方因子，那么miu(n)=0  m i u ( n ) = 0 。例如：miu(4),miu(12),miu(18)=0  m i u ( 4 ) , m i u ( 12 ) , m i u ( 18 ) = 0 。  
如果一个数不包含平方因子，并且有k个不同的质因子，那么miu(n)=(−1)k  m i u ( n ) = ( − 1 ) k 。  
例如：miu(2),miu(3),miu(30)=−1,miu(1),miu(6),miu(10)=1  m i u ( 2 ) , m i u ( 3 ) , m i u ( 30 ) = − 1 , m i u ( 1 ) , m i u ( 6 ) , m i u ( 10 ) = 1 。  
给出一个数n, 计算miu(n)  m i u ( n ) 。

**Input**  
输入包括一个数n，(2<=n<=109)  2 <= n <= 10 9 )

**Output**  
输出miu(n)。

**Input示例**  
5  
**Output示例**  
\-1

--------------------

根据定义直接写

#include<bits/stdc++.h>
    using namespace std;
    int miu(int n){
        int cnt=0;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                n/=i;
                cnt++;
                if(n%i==0)
                    return 0;
            }
        }
        if(n!=1)    cnt++;
        return cnt&1?-1:1;
    }
    
    int main(){
        int n;
        scanf("%d",&n);
        printf("%d\n",miu(n));
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，237人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1240 莫比乌斯函数(普通筛法)

[1240 莫比乌斯函数][1240] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [1240]: http://www.51

阳光穿透心脏的1/2处/ 2024年02月17日 23:17/ 0 赞/ 34 阅读

相关【题解】51Nod 1594 莫比乌斯反演

Updated：这只鸽子学会了LaTeX 题意求 $$\\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{n\} \\phi(gcd(\\

逃离我推掉我的手/ 2023年08月17日 16:49/ 0 赞/ 131 阅读

相关莫比乌斯反演学习小记

其实这东西压根还没学懂。。。先记录下学习资料 [莫比乌斯反演 - ACdreamer][- ACdreamer] [莫比乌斯反演入门 - qw4990的专栏][- q

ゞ浴缸里的玫瑰/ 2022年08月12日 00:08/ 0 赞/ 31 阅读

相关莫比乌斯反演

定理：F(n)和f(n)是定义在非负整数集合上的两个函数，并且满足条件F(n)=∑d|nf(d)，那么我们得到结论 f(n)=∑d|nμ(d)F(nd) 在上面的公式

谁践踏了优雅/ 2022年08月03日 00:15/ 0 赞/ 225 阅读

相关莫比乌斯反演

莫比乌斯函数![20140416160256500][]，它的定义如下：（1）若![20140416160429140][]，那么![201404161605

向右看齐/ 2022年06月11日 02:55/ 0 赞/ 209 阅读

相关 HDU-2841 Visible Trees (莫比乌斯反演)

Visible Trees There are many trees forming

谁践踏了优雅/ 2022年06月10日 13:53/ 0 赞/ 215 阅读

相关 HDU-1695 GCD(莫比乌斯反演)

GCD Given 5 integers: a, b, c, d, k, you're to

冷不防/ 2022年06月10日 12:15/ 0 赞/ 221 阅读

相关 51Nod 1240 莫比乌斯函数

滴，集训第十九天打卡。因为新开了group，所以之前的紫书训练也没人做了.. 现在是图论+数论比较多... 感觉上学期数据结构没学好...图论菜的不行=-=.. 51

ゝ一纸荒年。/ 2022年06月10日 00:08/ 0 赞/ 144 阅读

相关 ACdream 1114 Number theory （莫比乌斯反演）

题目链接： [ACdream 1114][] 题意：给你一个序列 a，求出这个序列中互质数的有多少对。其中所有的整数的都小于等于 222222 。题解：

╰半夏微凉°/ 2022年06月09日 05:25/ 0 赞/ 194 阅读

相关 51Nod 1240 莫比乌斯函数 ——————莫比乌斯函数

1240 莫比乌斯函数基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(

骑猪看日落/ 2022年05月15日 04:27/ 0 赞/ 238 阅读