bzoj2301

题解：

莫比乌斯反演

再加上一个分块

然后和上一题差不多了

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=;

ll ans1,ans2;

int sum[N],a,b,x,y,z,tot,T,cnt,miu[N],flag[N],p[N];

void init()

{

    miu[]=;

    sum[]=;

    for (int i=;i<N;i++)

     {

         if (!flag[i])

          {

              miu[i]=-;

              p[++tot]=i;

          }

         for (int j=;j<=tot;j++)

          {

              int k=p[j]*i;

              if (k>=N)break;

              flag[k]=;

              if (i%p[j]==)

               {

                   miu[k]=;

                   break;

               }

              miu[k]-=miu[i];

          }

     }

    for (int i=;i<N;i++)sum[i]=sum[i-]+miu[i];

}

ll find(int x,int y)

{

    if (x>y)swap(x,y);

    ll ans=;int j;

    for (int i=;i<=x;i=j+)

     {

        j=min(x/(x/i),y/(y/i));

        ans+=(ll)(sum[j]-sum[i-])*(x/i)*(y/i);

     }

    return ans;

}

int main()

{

    scanf("%d",&T);

    init();

    while (T--)

     {

         ans1=ans2=;

         scanf("%d%d%d%d%d",&a,&x,&b,&y,&z);

         x/=z;y/=z;a=(a-)/z;b=(b-)/z;

         ans1=find(x,y)-find(a,y)-find(x,b)+find(a,b);

         printf("%lld\n",ans1);

     }

}