51nod 1240 莫比乌斯函数

链接：莫比乌斯函数问题 - 51Nod http://www.51nod.com/onlineJudge/questionCode.html#!problemId=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示例

Output示例

-1

刚刚看这个，这里要计算不同质因子的个数并且判断每个质因子的个数是否大于1，那我们就用类似筛选质因子的方法，
在筛的同时判断是否有平方因子并且把n里的这个质因子除尽这里要注意最后的n是不是大于1
因为如果最后n介于i*i和（i+1）*（i+1）之间就会漏掉这一次计算，比如说14，第一次除去2，得7，但是7小于3*3，所以7这个质因子就会漏掉
所以最后要特判一下n。

#include<cstdio>
#include<cstring>
typedef long long ll;
ll n,m,k,t;
ll cal(ll n)
{
    ll m=0;//计数器 
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            m++;
            n/=i;
            if(n%i==0)//有平方因子 
            return -1;
        }
    }
    if(n>1)//特别判断 
    m++;
    return m;
}
int main()
{
    while(scanf("%lld",&n)!=EOF)
    {
        int ans=cal(n);
        if(ans==-1)
        printf("%d
",0);
        else if(ans%2)
        printf("%d
",-1);
        else
        printf("%d
",1);
    }
    return 0;
 }

当然，也可以这样写：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<cstdio>
#include<string>
#include<deque> 
using namespace std;
#define eps 1e-8
#define ll long long
#define INF 0x3f3f3f3f
int n,m,k,t;
int cal(int n)
{
    m=n;
    int num=0;
    for(int i=2;i<=(int)sqrt(m);i++)
    {
        if(m%i==0)
        {
            m/=i;
            num++;
            if(m%i==0)
            return 0;
        }
    }
    if(m>1)
    num++;
    if(num&1)
    return -1;
    else
    return 1;
}
int main()
{
    cin>>n;
    cout<<cal(n)<<endl;
    return 0;
}