Project Euler 193
题目
Squarefree Numbers
A positive integer is called
squarefree, if no square of a prime divides , thus are squarefree, but not .
How many squarefree numbers are there below ?
莫比乌斯函数
莫比乌斯函数,常用于容斥原理。
假设 的分解质因数为 ,那么莫比乌斯函数 函数值定义如下:
解决方案
基于容斥原理的思想,我们首先假设所有数都是无平方因子数,然后减去有 个质因子的 的数。在此减去过程中,会有 两个质因子的 的质数被重复减去,因此需要补回。。。
为了不重不漏,有平方因子数完全不参与上面的过程。
那么发现,只要有偶数个质因子的就会被增加,有奇数个质因子就会被减去。莫比乌斯函数恰好帮助我们表示了整个过程。
使用线性筛计算莫比乌斯函数:如果筛出来的是一个新质因子,那么对原来的莫比乌斯函数值乘 就可以得到新数的莫比乌斯函数值,如果是旧的质因子,那么直接赋 。
最终答案为:
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| #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); }
|