本文共 1019 字，大约阅读时间需要 3 分钟。

题目链接

题解

直接反演一下就好了，甚至都不用整除分块……

代码

#include 
   
    #include 
    
     int read(){
     int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
         if(ch=='-')        {
             f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
         x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=1000000;int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10];int getprime(){
     p[1]=mu[1]=1;  for(int i=2; i<=maxn; ++i)    {
         if(!p[i])        {
             prime[++cnt]=i;          mu[i]=-1;        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
             int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                 mu[x]=0;              break;            }          mu[x]=-mu[i];        }    }  return 0;}int n,m,k;long long ans;int main(){
     getprime();  n=read();  m=read();  k=read();  for(int i=1; i<=std::min(n,m)/k; ++i)    {
         ans+=1ll*mu[i]*(n/(k*i))*(m/(k*i));    }  printf("%lld\n",ans);  return 0;}
    
   

转载地址：https://blog.csdn.net/wang3312362136/article/details/85990943 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！