滴，集训第十九天打卡。
因为新开了group，所以之前的紫书训练也没人做了..
现在是图论+数论比较多...
感觉上学期数据结构没学好...图论菜的不行=-=..
51Nod 1240
莫比乌斯函数
详解后续放..在另一台电脑上...
#include <stdio.h>
#include <string.h>
int su[50010],sh[50010];
int get(int n)
{
int s=0,i,j;
for(i=0;sh[i]*sh[i]<=n;i++)
{
if(n%(sh[i]*sh[i])==0)
return 0;
if(n%sh[i]==0)
{
s++;
n/=sh[i];
}
}
if(n>0)
s++;
if(s&1)return -1;
else return 1;
}
int main()
{
int n,i,j,k=0;
memset(su,0,sizeof(su));
for(i=2;i<50010;i++)
{
if(!su[i])
{
sh[k++]=i;
for(j=i*2;j<50010;j+=i)
su[j]=1;
}
}
scanf("%d",&n);
printf("%d\n",get(n));
}
