//求单个值 ll getmob(ll a){ ll x=a,tmp=a; int cnt=0,now=0; for(ll j=2;j*j<=x;j++){ now=0; if(x%j==0){ while(x%j==0) now++,x/=j; if(now>1) return 0; cnt++; } } if(x!=1) cnt++; return (cnt&1)?-1:1; } int getmu(int n) { int v=1; for(int i=2;i*i<=n;i++) if(n%i==0) { v=-v;n/=i; if(n%i==0)return 0; } if(n!=1)v=-v; return v; } //最大可用范围[1,maxn),实际使用[1,maxn); //初始化要求vis,mu至0,maxn const int maxn; int mu[maxn],sum[maxn],prime[maxn]; bool vis[maxn]; void mobius_ini(){ mu[1]=1; prime[0]=0; for(int i=2;i<maxn;i++){ if(!vis[i]){ mu[i]=-1; prime[++prime[0]]=i; } for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){ vis[i*prime[j]]=true; if(i%prime[j]) mu[i*prime[j]]=-mu[i]; else{ mu[i*prime[j]]=0; break; } } } for(int i=1;i<maxn;i++)sum[i]=sum[i-1]+mu[i]; } /* 01: 1 02:-1 03:-1 04: 0 05:-1 06: 1 07:-1 08: 0 09: 0 10: 1 11:-1 12: 0 13:-1 14: 1 15: 1 16: 0 17:-1 18: 0 19:-1 20: 0 21: 1 22: 1 23:-1 24: 0 25: 0 26: 1 27: 0 28: 0 29:-1 30:-1 31:-1 32: 0 33: 1 34: 1 35: 1 36: 0 37:-1 38: 1 39: 1 40: 0 41:-1 42:-1 43:-1 44: 0 45: 0 46: 1 47:-1 48: 0 49: 0 50: 0 51: 1 52: 0 53:-1 54: 0 55: 1 56: 0 57: 1 58: 1 59:-1 60: 0 61:-1 62: 1 63: 0 64: 0 65: 1 66:-1 67:-1 68: 0 69: 1 70:-1 71:-1 72: 0 73:-1 74: 1 75: 0 76: 0 77: 1 78:-1 79:-1 80: 0 81: 0 82: 1 83:-1 84: 0 85: 1 86: 1 87: 1 88: 0 89:-1 90: 0 91: 1 92: 0 93: 1 94: 1 95: 1 96: 0 97:-1 98: 0 99: 0 */