莫比乌斯

#include <cstdio>

#include <cstring>

#include<iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN=100000;

bool check[MAXN+10];

int prime[MAXN+10];

int mu[MAXN+10];

void mobi()

{

    memset(check,false,sizeof(check));

    mu[1] = 1;

    int tot = 0;

    for(int i = 2; i <= MAXN; i++)

    {

        if( !check[i] )

        {

            prime[tot++] = i;

            mu[i] = -1;

        }

        for(int j = 0; j < tot; j++)

        {

            if(i * prime[j] > MAXN) break;

            check[i * prime[j]] = true;

            if( i % prime[j] == 0)

            {

                mu[i * prime[j]] = 0;

                break;

            }

            else

            {

                mu[i *prime[j]] = -mu[i];

            }

        }

    }

}

int main()

{

    mobi();

    int n;cin>>n;

    cout<<mu[n]<<endl;

}

int main()

{

    int n;cin>>n;

    if(n==1)return cout<<1<<endl,0;

    int ans=0;

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

    {

        int cnt=0;

        while(n%i==0)n/=i,cnt++;

        if(cnt>1)return cout<<0<<endl,0;

        ans+=cnt;

    }

    if(n>1)ans++;

    if(ans&1)return puts("-1"),0;

    return cout<<1<<endl,0;

}

©著作权归作者所有：来自51CTO博客作者qinXpeng的原创作品，如需转载，请注明出处，否则将追究法律责任