题目链接

题解

$\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$

即

b c + a c = (a + b) c = a b

设

g=\gcd(a,b),A=\frac{a}{g},B=\frac{b}{g}

，则有

g(A+B)c=ABg^2\\ (A+B)c=ABg

由于

c\not= 0,g\not= 0

\frac{A+B}{g}=\frac{AB}{c}=k

假设

k\geq 2

，那么

A B = k c

，由于

\gcd(A,B)=1

，因此

k ∣ A

或

k ∣ B

，不可能同时满足，那么

k\nmid A+B

，但是

A + B = k g

，推出矛盾，因此

k = 1

。

那么

A + B = g, A B = c

如果已经得到了

g

和

A

，满足题目要求的条件就是

\gcd(A,g-A)=1,(g-A)A\leq n,Ag\leq n,(g-A)g\leq n

容易发现

\gcd(A,g)=1,2\leq g\leq \sqrt{2n},\max(g-\lfloor\frac{n}{g}\rfloor,1)\leq A\leq \min(\lfloor \frac{n}{g}\rfloor,g-1)

因此反演求出一段区间内与

g

互质的数的个数即可。

注意这题卡时限，必须预处理出每个数的约数，还要用邻接表存，不能用vector，否则会TLE……

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       template
       
        T read(){     T x=0;  int 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=1414213;const int maxm=13288457;int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10],pre[maxm+10],now[maxn+10],son[maxm+10],tot;int add(int a,int b){     pre[++tot]=now[a];  now[a]=tot;  son[tot]=b;  return 0;}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];        }    }  for(int i=1; i<=maxn; ++i)    {         if(!mu[i])        {             continue;        }      for(int j=1; j<=maxn/i; ++j)        {             add(i*j,i);        }    }  return 0;}inline long long solve(int x,int l,int r){     long long ans=0;  for(int i=now[x]; i; i=pre[i])    {         int k=son[i];      ans+=mu[k]*(r/k-l/k);    }  return ans;}long long n;int main(){     getprime();  n=read
        
         (); long long ans=0; int mx=sqrt(2*n)+0.5; for(int i=2; i<=mx; ++i) { ans+=solve(i,std::max(1ll,i-n/i)-1,std::min(n/i,i-1ll)); } printf("%lld\n",ans); return 0;}