[XJTUPC2024] 筛法

在算法竞赛的数论知识中，我们接触过埃拉托斯特尼筛法、线性筛法、莫比乌斯反演、杜教筛、Powerful Number 筛、Min\_25 筛、洲阁筛等算法来帮助我们优化一些求和/连乘的复杂度，那么现在问题来了，今天这道题将会使用到上述的哪个算法呢？ 现在给定正整数 $n$，需要你求 $$ \sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor \dfrac{n}{\max(i,j)}\rfloor [i \perp j] $$ 其中 $[i \perp j]$ 表示 $i,j$ 是否互素，即当 $\gcd(i,j)=1$ 时，$[i \perp j]$ 的值为 $1$，其余情况其值为 $0$。

输入一行一个正整数 $n$ ($1\le n \le 10^9$)。

输出一行一个整数，表示这个和式的结果。

2

4