题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2301
继续学习PoPoQQQ大爷的ppt.....
代码：
#include<bits/stdc++.h> using namespace std; const int MAXN=50005; typedef long long ll; bool check[MAXN+10]; int prime[MAXN+10]; int mu[MAXN+10]; int sum[MAXN+10]; void Moblus() { memset(check,false,sizeof(check)); mu[1]=1; int tot=0; for(int i=2;i<=MAXN;i++) { if(!check[i]) { prime[tot++]=i; mu[i]=-1; } for(int j=0;j<tot;j++) { if(i*prime[j]>MAXN) break; check[i*prime[j]]=true; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } else { mu[i*prime[j]]=-mu[i]; } } } for(int i=1;i<=MAXN;i++) { sum[i]=sum[i-1]+mu[i]; } } ll cal(ll n,ll m) { ll ret=0; int last=1; if(n>m) swap(n,m); for(int i=1;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); ret+=(n/i)*(m/i)*(sum[last]-sum[i-1]); } return ret; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,a,b,c,d,k; Moblus(); scanf("%d",&n); while(n--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); ll ans=0; a--;c--; a/=k;b/=k;c/=k;d/=k; ans+=cal(b,d)-cal(a,d)-cal(b,c)+cal(a,c); printf("%lld\n",ans); } return 0; }
