推荐一个大佬的两篇文章

函数(Möbius function)是指以下的函数：

在这里，λ(

n)是

莫比乌斯函数是一个数论函数，它同时也是一个积性函数(i.e.

μ(

ab) =

μ(a)

μ(

b), a,b互质)

当n不等于1时，n所有因子的莫比乌斯函数值的和为0，

莫比乌斯函数完整定义的通俗表达：

1）莫比乌斯函数μ(n)的定义域是N

2）μ(1)=1

3）当n存在平方因子时，μ(n)=0

4）当n是素数或奇数个不同素数之积时，μ(n)=-1

5）当n是偶数个不同素数之积时，μ(n)=1

前50个莫比乌斯函数值绘制如下：

所以acm的莫比乌斯函数就是和素数有关的函数？

所以求n的莫比乌斯函数就很简单了，统计素因子个数，统计每个素因子的个数，及时返回

#include
       
        int num;int miu(int n) {    for(int i=2; i*i<=n; i++) {        if(n%i==0) {            num++;            int cnt=0;            while(n%i==0) {                n/=i;                cnt++;            }            if(cnt>1)                return 0;        }    }    return (num&1)?1:-1;}int main() {    int n;    while(~scanf("%d",&n)) {        num=0;        printf("%d\n",miu(n));    }}