P10532 [XJTUPC 2024] Sieve Method

In number theory for algorithm competitions, we have encountered algorithms such as the Sieve of Eratosthenes, the linear sieve, Möbius inversion, the Du Jiao sieve, the Powerful Number sieve, the Min\_25 sieve, and the Zhou Ge sieve to help optimize the complexity of some summations or products. Now here comes the question: which of the above algorithms will be used in today’s problem? Given a positive integer $n$, you need to compute $$ \sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor \dfrac{n}{\max(i,j)}\rfloor [i \perp j] $$ where $[i \perp j]$ indicates whether $i$ and $j$ are coprime. That is, when $\gcd(i,j)=1$, the value of $[i \perp j]$ is $1$; otherwise, its value is $0$.

One line contains a positive integer $n$ ($1\le n \le 10^9$).

Output one line containing an integer, representing the result of the above summation.

Translated by ChatGPT 5