题目 AC代码
#include<iostream>//算法 #include<cstdio> #include<climits> #include<algorithm> #include<cstring> typedef long long ll; using namespace std; const int maxn=10000005; int T,a,b,c,d,e,tot; long long ans1,ans2; bool is[maxn]; int pri[maxn],miu[maxn]; void init() //首先把莫比乌斯函数筛出来 { miu[1]=1;//n=1时， 莫比乌斯函数为1（1） for(int i=2; i<=10000000; i++) { if(!is[i]) { pri[++tot]=i; miu[i]=-1; } for(int j=1; j<=tot; j++) { int k=pri[j]*i; if(k>10000000)break; is[k]=1; if(i%pri[j]==0) { miu[k]=0;//（2） break; } else miu[k]=-miu[i];//（3），与欧拉法素数的筛选的三个区别 } } } int main() { int i,j; init(); scanf("%d%d%d%d",&a,&b,&c,&d); ll ans=0; for(int i=1; i<=min(b,d); i++) ans+=(ll)miu[i]*(b/i-(a-1)/i)*(d/i-(c-1)/i); printf("%lld\n",ans); return 0; }