考虑对于每个点对 $(a,b)$ 算出有多少对 $(i,j)$ 途径了这个状态。从 $(a,b)$ 倒推。其可以到达两个状态 $(a,a+b)$ 和 $(a+b,b)$。构成了一个树形结构。

考虑将中间相同的元素缩起来，可以看作一个序列。一开始是 $(a,b)$，后来是 $(a,a+b,b)$。每一轮在两个数中间插入它们的和。

在每次新加入的位置统计贡献，那么所求即为：这个过程不断持续下去，得到的序列中 $\le N$ 的数的个数。观察一下得到的序列。我们可以把每个数表示为 $(x,y)=ax+by$。得到如下性质：

任意时刻，对于两个相邻的数 $(a,b),(c,d)$ 有 $ad-bc=1$。所有满足 $ad-bc=1$ 的非负整数 $a,b,c,d$ 都会出现在序列中。由裴蜀定理，我们可以得到：所有满足 $\gcd(i,j)=1$ 的 $i,j$，$ai+bj$ 都会出现在序列中。

所以答案即为 $g(n,a,b)=\sum_{i=1}^{n}\sum_{j=1}^n[\gcd(i,j)=1][ai+bj\le n]$。

所求即为 $f(n)=\sum_{i=1}^n\sum_{j=1}^ng(n,i,j)$。

然后随便推了。

考虑莫比乌斯反演。设 $G(n,a,b)=\sum_{i=1}^{n}\sum_{j=1}^n[ai+bj\le n]=\sum_{i=1}^n\lfloor\frac{n-ai}{b}\rfloor$。则 $g(n,a,b)=\sum_{i=1}^n\mu(i)G(\lfloor\frac{n}{i}\rfloor, a, b)$。

$f(n)=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\mu(k)G(\lfloor\frac{n}{k}\rfloor, i, j)$。

$f(n)=\sum_{k=1}^n\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}G(\lfloor\frac{n}{k}\rfloor,i,j)$。

设 $F(n)=\sum_{i=1}^n\sum_{j=1}^nG(n,i,j)$。

展开，$F(n)=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\lfloor\frac{n-ki}{j}\rfloor=\sum_{k=1}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}s(n-ki)$。其中 $s(i)$ 表示 $1\sim i$ 的因子数之和。

使用数论分块计算即可，时间复杂度 $O(n\log n)$​。如果使用理论复杂度相同的 NTT，可以获得低于 $100$ 的分数。