51nod1240莫比乌斯函数

By admin in 亚洲必赢官网app on 2019年1月15日

莫比乌斯函数,由德意志地医学家和天国学家莫比乌斯指出。梅滕斯(Mertens)首先使用μ(n)(miu(n))作为莫比乌斯函数的符号。(据说,高斯(Gauss)比莫比乌斯早三十年就曾考虑过那么些函数)。

 

实际定义如下:

假若一个数包含平方因子,那么miu(n) = 0。例如:miu(4), miu(12), miu(18) =
0。

万一一个数不带有平方因子,并且有k个不同的质因子,那么miu(n) =
(-1)^k。例如:miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。

付出一个数n, 统计miu(n)。

Input

输入包括一个数n,(2 <= n <= 10^9)

Output

输出miu(n)。

Input示例

5

Output示例

-1

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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 亚洲必赢手机官网 版权所有