题目链接

题解

对于一对$(a,b)$满足$a+b\mid ab$，假设$d=\gcd (a,b),a=xd,b=yd$，那么

xd+yd∣xyd2x+y∣xydx+y∣d xd+yd\mid xyd^2\\ x+y\mid xyd\\ x+y\mid d xd+yd∣xyd2x+y∣xydx+y∣d

设m=⌊n⌋m=\lfloor\sqrt{n}\rfloorm=⌊n​⌋答案就是

∑j=1m∑i=1j−1⌊ni+j⌋[gcd⁡(i,j)=1]=∑d=1mμ(d)∑j=1⌊m/d⌋∑i=1j−1⌊nd2(i+j)⌋ \begin{aligned} & \sum_{j=1}^{m}\sum_{i=1}^{j-1}\lfloor\frac{n}{i+j}\rfloor [\gcd(i,j)=1]\\ = & \sum_{d=1}^{m}\mu(d)\sum_{j=1}^{\lfloor m/d\rfloor}\sum_{i=1}^{j-1}\lfloor\frac{n}{d^2(i+j)}\rfloor \end{aligned} =​j=1∑m​i=1∑j−1​⌊i+jn​⌋[gcd(i,j)=1]d=1∑m​μ(d)j=1∑⌊m/d⌋​i=1∑j−1​⌊d2(i+j)n​⌋​

复杂度大概是O(n3/4)O(n^{3/4})O(n3/4)的，这个请大家自行证明。

代码

#include 
    
     #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=65536;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;}long long calc(int n,int d){
      long long ans=0;  for(int i=1; i<=d; ++i)    {
          int t=n/i;      for(int l=i+1,r; (l<(i<<1))&&(l<=t); l=r+1)        {
              r=std::min((i<<1)-1,t/(t/l));          ans+=1ll*(r-l+1)*(t/l);        }    }  return ans;}int n,s;int main(){
      getprime();  n=read();  s=sqrt(n);  long long ans=0;  for(int i=1; i<=s; ++i)    {
          ans+=mu[i]*calc(n/i/i,s/i);    }  printf("%lld\n",ans);  return 0;}