洛谷P2522 [HAOI2011]Problem b（莫比乌斯反演）

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #define ll long long
 5 using namespace std;
 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 7 char buf[1<<21],*p1=buf,*p2=buf;
 8 inline int read(){
 9     #define num ch-‘0‘
10     char ch;bool flag=0;int res;
11     while(!isdigit(ch=getc()))
12     (ch==‘-‘)&&(flag=true);
13     for(res=num;isdigit(ch=getc());res=res*10+num);
14     (flag)&&(res=-res);
15     #undef num
16     return res;
17 }
18 const int N=5e5+5;
19 int p[N],m,vis[N],mu[N],sum[N],a,b,c,d,k;
20 void init(int n){
21     mu[1]=1;
22     for(int i=2;i<=n;++i){
23         if(!vis[i]) p[++m]=i,mu[i]=-1;
24         for(int j=1;j<=m&&p[j]*i<=n;++j){
25             vis[i*p[j]]=1;
26             if(i%p[j]==0) break;
27             mu[i*p[j]]=-mu[i];
28         }
29     }
30     for(int i=1;i<=n;++i) sum[i]=sum[i-1]+mu[i];
31 }
32 ll calc(int a,int b){
33     int lim=min(a,b);ll res=0;
34     for(int l=1,r;l<=lim;l=r+1){
35         r=min(a/(a/l),b/(b/l));
36         res+=1ll*(a/(l*k))*(b/(l*k))*(sum[r]-sum[l-1]);
37     }
38     return res;
39 }
40 int main(){
41 //    freopen("testdata.in","r",stdin);
42     int T=read();init(50000);
43     while(T--){
44         a=read(),b=read(),c=read(),d=read(),k=read();
45         printf("%lld\n",calc(b,d)-calc(b,c-1)-calc(a-1,d)+calc(a-1,c-1));
46     }
47     return 0;
48 }