D - GCD

HDU - 1695

• 思路： 都 除以 k 后转化为  1-b/k    1-d/k中找互质的对数，但是需要去重一下  （x，y）  （y，x） 这种情况。
• 这种情况出现 x  ，y 肯定 都在 min  （b/k， d/k）  ，所以 奇数 最后 减去 一半 即可。

• #include<bits/stdc++.h>
  
  using namespace std;
  
  #define ll long long
  
  #define maxn 1234567
  
  bool vis[maxn+10];
  
  ll t,n,m,prime[maxn+10];
  
  ll mu[maxn+10],ans,a,b,c,d,k,sum;
  
  void getphi()
  
  {
  
      int cnt=0;
  
      mu[1]=1;
  
      for(int i=2; i<maxn; i++)
  
      {
  
          if(!vis[i])
  
          {
  
              prime[++cnt]=i;
  
              mu[i]=-1;
  
          }
  
          for(int j=1; j<=cnt&&i*prime[j]<maxn; j++)
  
          {
  
              vis[i*prime[j]]=1;
  
              if(i%prime[j]==0)
  
              {
  
                  mu[i*prime[j]]=0;
  
                  break;
  
              }
  
              else mu[i*prime[j]]=-mu[i];
  
          }
  
      }
  
  }
  
  int main()
  
  {
  
      getphi();
  
      scanf("%lld",&t);
  
      for(int q=1; q<=t; q++)
  
      {
  
          ans=sum=0;
  
          scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
  
          if(k==0)
  
          {
  
              printf("Case %d: 0\n",q);
  
              continue;
  
          }
  
          b/=k,d/=k;
  
          n=min(b,d);
  
          for(int i=1; i<=n; i++)
  
          {
  
              ans+=(ll)mu[i]*(b/i)*(d/i);
  
              sum+=(ll)mu[i]*(n/i)*(n/i);
  
          }
  
          printf("Case %d: %lld\n",q,ans-sum/2);
  
      }
  
      return 0;
  
  }