BZOJ2301：莫比乌斯反演+二维容斥解决GCD范围计数

 1 #include<cstdio>
 2 #include<algorithm>
 3 using std::min;
 4 const int maxn=60005;
 5 int cnt,a,b,c,d,k;
 6 long long ans;
 7 bool vis[maxn];
 8 int mu[maxn],sum[maxn];
 9 long long prim[maxn];
10 inline long long read()
11 {
12     long long x=0,f=1;char ch=getchar();
13     while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)f=-1;ch=getchar();}
14     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
15     return x*f;
16 }
17 void get_mu(long long x)
18 {
19     mu[1]=1;
20     for(long long i=2;i<=x;i++)
21     {
22         if(!vis[i]){mu[i]=-1;prim[++cnt]=i;}
23         for(long long j=1;j<=cnt&&i*prim[j]<=x;j++)
24         {
25             vis[i*prim[j]]=1;
26             if(i%prim[j]==0) break;
27             else mu[i*prim[j]]=-mu[i];
28         }
29     }
30     for(long long i=1;i<=x;i++) sum[i]=sum[i-1]+mu[i];
31 }
32 long long calc(int a,int b)
33 {
34     int max_rep=min(a,b);
35     long long ret=0;
36     for(int l=1,r;l<=max_rep;l=r+1)
37     {
38         r=min(a/(a/l),b/(b/l));
39         ret+=(sum[r]-sum[l-1])*(1ll*a/(1ll*l*k))*(1ll*b/(1ll*l*k));
40     }
41     return ret;
42 }
43 int main()
44 {
45     int T;
46     T=read();
47     get_mu(50000);
48     while(T--)
49     {
50         a=read();b=read();c=read();d=read(),k=read();
51         ans=calc(b,d)-calc(b,c-1)-calc(a-1,d)+calc(a-1,c-1);
52         printf("%lld\n",ans);
53     }
54     return 0;
55 }