51nod 1240 莫比乌斯函数【数论+莫比乌斯函数】

1240 莫比乌斯函数

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

 收藏

 关注

莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(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

【分析】：

（1）如果这个数n能整除某个数的平方，那么函数值就为0；

（2）否则判断它的因子个数（k）的奇偶性，函数值为（-1）^k；

 【代码】：

#include<string.h>

#include<stdlib.h>

#include<queue>

#include<stack>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<stdlib.h>

#include<cmath>

#include<string>

#include<algorithm>

#include<iostream>

#define exp 1e-10

#define MAX(a,b) ((a)>(b)?(a):(b))

using namespace std;

const int N = ;

const int M = ;

const int inf = ;

const int mod = ;

int fun(int n)

{

    int cnt;

    int sum=;

    for(int i=;i*i<=n;i++)

    {

        cnt=;

        if(n%i==)

        {

            sum++;//记录质因子个数

            while(n%i==)//计算因子个数

            {

                n=n/i;

                cnt++;

            }

            if(cnt>=)//若此因子出现次数大于等于两次，则因子必存在i的平方

                return ;

        }

    }

    if(n!=)

        sum++;

    return (sum%)?-:;//如果因子个数为奇数则函数值为-1 ，如果因子个数为偶数则函数值为1

}

int main()

{

    int n;

    while(~scanf("%d",&n))

        printf("%d\n",fun(n));

    return ;

}