【51Nod】1240 - 莫比乌斯函数（线性筛）

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

输出miu(n)。

5

-1

#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int miu(int n)
{
	int ant = 0;
	for (int i = 2 ; i <= sqrt(n) ; i++)
	{
		if (n % i == 0)
		{
			n /= i;
			ant++;
			if (n % i == 0)
				return 0;
		}
	}
	if (n > 1)
		ant++;
	if (ant & 1)
		return -1;
	else
		return 1;
}
int main()
{
	int n;
	scanf ("%d",&n);
	printf ("%d\n",miu(n));
	return 0;
}