题目概述

求 ${1\over a}+{1\over b}={1\over c}(a,b,c\in N^{*},a,b,c\le n)$ 解的个数。

解题报告

被学弟安利了这题（学弟秒掉了来嘲讽我）。首先三个变量一副不可做的样子，转化一下：

$$ d=(a,b),a=a'd,b=b'd\\ {1\over d}({1\over a'}+{1\over b'})={1\over c}\\ {1\over a'}+{1\over b'}={d\over c}\\ {a'+b'\over a'b'}={d\over c} $$

也就是说原式等价于 ${1\over (x+y)x}+{1\over (x+y)y}={1\over xy},(x,y)=1$ 只要求出 $(x,y)$ 的个数就行了。

那么就是求 $\sum_{i=1}^{n}\sum_{j=1}^{i}[(i,j)=1\land (i+j)i\le n]$ 。

处理一下边界之后：$\sum_{i=1}^{\sqrt n}\sum_{j=1}^{min\{i,{n-i^2\over i}\}}e[(i,j)]$ ，上莫比乌斯函数：$\sum_{k=1}^{\sqrt n}\mu(k)\lfloor{\sqrt n\over k}\rfloor sum(j)$ 。

由于 $j$ 的范围跟着 $i$ 变，所以 $sum(j)$ 不能直接得出，怎么办呢？大不了枚举 $i$ 啊，调和级数大法好。

示例程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000000;

LL n,ans;int S,u[maxn+5],p[maxn+5];bool pri[maxn+5];

inline void Make(int n){
    pri[0]=pri[1]=true;u[1]=1;
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,u[i]=-1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            if (i%p[j]) u[t]=-u[i],pri[t]=true; else {u[t]=0;pri[t]=true;break;}
    }
}
#define Lim(x) (min((LL)(x),(n-(LL)(x)*(x))/(x)))
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%lld",&n);S=sqrt(n);Make(S);
    for (int k=1;k<=S;k++) for (int i=k;i<=S;i+=k) ans+=(Lim(i)/k)*u[k];
    return printf("%lld\n",(ans<<1)-1),0;
}