PE193

求$<2^{50}$的squarefree number的数量

做法

容斥原理，莫比乌斯函数

莫比乌斯函数

假设$n$的质因数分解为$n={p_1}^{e_1}\cdot {p_2}^{e_2}\cdot \cdot \cdot {p_k}^{e_k}$

$$\mu (n)=\{\begin{array}{lcl}1& & n==1\\ 0& & \exists m\in [1,k],e_m\ge 2\\ (-1{)}^k& & \end{array}$$

容斥原理

设$N=2^{50}$

• 我们考虑所有是$2^2$的倍数的数，比如$4,8,12,\mathrm{16...}$这些都有平方因子，都应该减去,这些数有$\lfloor \frac{N}{2^2}\rfloor 个$
• 同样的，考虑$3^2$的倍数的数, 比如$9,18,27,\mathrm{36...}$也都有平方因子，也要减去，有$\lfloor \frac{N}{3^2}\rfloor 个$
• 考虑同时是$2^2和3^2$的倍数的数，也就是$6^2$的倍数的数，比如$36,72,\mathrm{108...}$他们在上述计算的时候被减去了两次，因此需要加回来

这就是容斥定理的思想
总结下来：对于有一个质因子的数，应该减去，两个质因子的应该加上，考虑扩展同样的思路，三个质因子的数，需要减去… 这个正好就是上述的莫比乌斯函数的值

最终答案可以表示为

$$ans=\sum _{k=1}^{\lfloor \sqrt{N}\rfloor }\lfloor \frac{N}{k^2}\rfloor \cdot \mu (k)$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1ll<<50;
const ll M=sqrt(N);
int mu[M+1];
int pr[M+1],v[M+1],m=0;
int main(){mu[1]=1;for(int i=2;i<=M;i++){if(v[i]==0){pr[++m]=i;v[i]=i;mu[i]=-1;}for(int j=1;j<=m;j++){if(pr[j]>v[i]||pr[j]>M/i) break;v[i*pr[j]]=pr[j];mu[i*pr[j]]=(v[i]==pr[j]?0:-mu[i]);}}ll ans=0;for(int i=1;i<=M;i++)ans+=1ll*mu[i]*(N/(1ll*i*i));printf("%lld\n",ans);
}