∑MathAdvanced

Divisor Function Sums

Key Points

•
Summing the divisor function d(i) up to n equals counting lattice points under the hyperbola $x y \leq n$ , which can be done in O(√n) using floor-division blocks.
•
The prefix sum of Euler’s totient Φ(n) = ∑_{ $i=1}^{n}$ $φ (i)$ can be computed sublinearly via Möbius inversion: Φ(n) = ∑_{ $d=1}^{n}$ $μ (d)$ T(⌊n/d⌋), where T(m) = m(m+1)/2.
•
The Mertens function M(n) = ∑_{ $i=1}^{n}$ $μ (i)$ can be computed in about O( $n^{2/3}$ ) using a sieve for small values and a memoized floor-division recursion for large values.
•
The key trick is that ⌊n/i⌋ takes only about 2√n distinct values, so we can sum over O(√n) intervals instead of n individual terms.
•
Dirichlet convolutions connect these functions: $d = 1 * 1$ and φ = μ * id, which drive the block-sum formulas.
•
Sublinear approaches rely on combining a small prime sieve with divide-and-conquer over integer divisions, not on iterating all $i \leq n$ .
•
For competitive programming, these methods let you handle n up to around 10^10–10^12 within time and memory limits if implemented carefully.
•
Choose integer types carefully (64-bit) and group ranges [l, r] where ⌊n/l⌋ is constant to avoid TLE.

Prerequisites

→Number theory basics (primes, gcd) — Understanding μ, φ, and coprimality relies on prime factorization and gcd properties.
→Big-O notation and floor function properties — Block decomposition depends on how ⌊n/i⌋ behaves and asymptotic reasoning for performance.
→Dirichlet convolution and Möbius inversion — Key identities (d = 1 * 1 and φ = μ * id) underpin the transformation of sums.
→Sieve of Eratosthenes / linear sieve — Efficiently computing μ up to a cutoff requires sieving primes and multiplicative functions.
→Handling 64-bit arithmetic — Intermediate values can overflow 32-bit types; correct typing prevents wrong answers.

Detailed Explanation

Tap terms for definitions

01Overview

Divisor function sums are classic number-theoretic prefix sums that frequently appear in counting problems and competitive programming: S_d(n) = ∑{i=1}^{n} d(i) (number of divisors), Φ(n) = ∑{i=1}^{n} φ(i) (Euler’s totient), and M(n) = ∑_{i=1}^{n} μ(i) (Mertens function). A naïve approach iterating i = 1..n is too slow for large n. The breakthrough is to observe that many terms repeat when seen through the lens of floor division: the value ⌊n/i⌋ changes only O(√n) times. This lets us replace long sums with a short loop over blocks of indices, each block contributing the same value. Furthermore, relationships via Dirichlet convolution (like d = 1 * 1 and φ = μ * id) and Möbius inversion turn hard sums into manageable expressions involving μ and simple polynomials such as triangular numbers. Combining these ideas with a sieve for small values and recursion for large arguments yields sublinear algorithms. These techniques are standard for counting lattice points under hyperbolas, coprime pairs, and for evaluating arithmetic function prefix sums up to huge n (10^10–10^12) within strict time limits.

02Intuition & Analogies

Picture the grid of integer points (x, y) with x, y ≥ 1. The inequality xy ≤ n draws a rectangular hyperbola. Counting all grid points under this curve equals the total number of divisor pairs of numbers up to n: each k ≤ n contributes a point for each divisor d of k via the pair (d, k/d). That count is exactly S_d(n) = ∑ d(k), so we have a geometric view of the sum. Now notice a symmetry: for small x, y can be large, but as x grows, y shrinks. The heights y = ⌊n/x⌋ stay constant over stretches of x because floor division doesn’t change every step. If ⌊n/l⌋ = ⌊n/(l+1)⌋ = … = ⌊n/r⌋ = t, we can add t for each index in [l, r] in one go, instead of one at a time. That’s the block (or two-pointer) trick. For Φ(n), imagine counting coprime pairs by grouping them by their greatest common divisor d. If gcd(a, b) = d, then a = d·a′, b = d·b′ and gcd(a′, b′) = 1. Möbius inversion acts like an inclusion–exclusion filter that cancels pairs which share unwanted common factors, leaving only the coprime ones. It turns sums over φ into sums over μ weighted by simple counts like triangular numbers or squares of floors. The Mertens function M(n) is just the running total of μ up to n; it captures how often inclusion beats exclusion up to each threshold. Because the same floor values repeat, you can compute M(n) recursively by subtracting big chunks corresponding to these repeated values without descending to every integer.

03Formal Definition

Let d(n) denote the number of positive divisors of n,

φ (n)

Euler’s totient (the count of integers 1 ≤

k \leq n

with gcd(k, n) = 1), and

μ (n)

the Möbius function (

μ (n)

= 0 if n has a squared prime factor,

μ (n)

= (−1)^k if n is the product of k distinct primes, and

μ (1)

= 1). Define their prefix sums:

S_{d}

(n) = ∑_{

k=1}^{n}

d(k), Φ(n) = ∑_{

k=1}^{n}

φ (k),

and M(n) = ∑_{

k=1}^{n}

μ (k) .

Dirichlet convolution of arithmetic functions f and g is (f * g)(n) =

\sum_{d ∣ n}

f(d) g

\frac{n}{d}

. Known identities:

d = 1 * 1

and φ = μ * id, where id(n) = n. These yield summation transforms such as ∑_{

k=1}^{n}

φ (k)

= ∑_{

d=1}^{n}

μ (d)

∑_{

m=1}^{⌊n/d⌋}

m. Another standard identity counts coprime pairs: ∑_{

i=1}^{n}

∑_{

j=1}^{n}

[gcd(i, j) = 1] = ∑_{

d=1}^{n}

μ (d)

⌊n/d⌋^2. The block decomposition relies on the property that for a fixed n, the value q = ⌊n/i⌋ remains constant over an interval [l, r] with r = ⌊n/q⌋, leading to O(√n) distinct q values. Finally, M(n) satisfies the recursion M(n) = 1 − ∑_{

k=2}^{n}

M(⌊n/k⌋), which, when grouped by equal floor values, can be computed in about O(

n^{2/3}

) with memoization and a small sieve.

04When to Use

Use block decomposition whenever you face sums that involve terms like ⌊n/i⌋, counts of divisors, or counts of pairs (i, j) constrained by i·j ≤ n. This includes computing S_d(n), counting lattice points under hyperbolas, and problems reducible to these forms. Apply Möbius inversion and μ-based formulas when you need to count coprime structures (e.g., pairs, reduced fractions) or to compute Φ(n) quickly for large n where sieving φ up to n is infeasible. The Mertens recursion with memoization is the right tool when you need M(n) or any sum that can be expressed as a short sum of M(⌊n/t⌋) values; it shines for n up to about 10^10–10^12 within time limits common in programming contests. Choose the approach based on constraints: for n ≤ 10^7, a direct linear sieve for μ or φ may suffice. For n around 10^9 and beyond, rely on the O(√n) lattice-point method for S_d(n) and the O(n^{2/3}) memoized recursion for M and Φ. Also use these methods whenever memory is tight, since they store only O(n^{2/3}) or O(√n) precomputed values rather than arrays of size n.

⚠️Common Mistakes

Common pitfalls include: (1) Forgetting 64-bit types. Quantities like ∑ d(i) can exceed 32-bit limits even for n around 10^6; always use long long (or __int128 for intermediate products). (2) Off-by-one errors in block loops. When grouping [l, r] with q = ⌊n/l⌋ and r = ⌊n/q⌋, ensure the next l is r + 1; otherwise you will skip or double-count indices. (3) Misusing Möbius inversion. Ensure the exact identity you apply is correct; for Φ(n) the right formula is Φ(n) = ∑_{d=1}^{n} μ(d) · T(⌊n/d⌋), with T(m) = m(m+1)/2, not squares. (4) Underestimating memory/time of sieves. A sieve up to n for n ≈ 10^10 is impossible; even up to n^{2/3} may be too large. Pick a practical cutoff (like n^{1/2} to n^{2/3}) and test within your memory budget. (5) Missing memoization in Mertens recursion, leading to exponential recomputation. Use unordered_map<long long, long long> to cache M(x) for large x. (6) Ignoring constant factors. While O(n^{2/3}) is sublinear, it can still be heavy; micro-optimizations like precomputing triangular numbers in-place, minimizing hash lookups, and avoiding unnecessary casts make a difference. (7) Using double-based pow for limits without careful casting can cause rounding errors; compute integer thresholds robustly (e.g., with integer cube root or binary exponentiation).

Key Formulas

Divisor-sum hyperbola identity

k = 1 \sum n d (k) = i = 1 \sum n ⌊ \frac{n}{i} ⌋

Explanation: Each i contributes the number of $m u lt i pl es \leq n$ , which equals ⌊n/i⌋. This counts lattice points (i, j) with i· $j \leq n$ and equals the sum of divisors over 1..n.

Totient prefix via Möbius

Φ (n) = k = 1 \sum n φ (k) = d = 1 \sum n μ (d) T (⌊ \frac{n}{d} ⌋), T (m) = \frac{m ( m + 1 )}{2}

Explanation: Using φ = μ * id and changing variables $k = d m$ yields a sum over $μ (d)$ times the triangular number of ⌊n/d⌋. This avoids sieving φ up to n.

Mertens function

M (n) = k = 1 \sum n μ (k)

Explanation: Defines the prefix sum of the Möbius function. It serves as a building block for many block-sum formulas, enabling fast range sums of $μ .$

Mertens recursion

M (n) = 1 - k = 2 \sum n M (⌊ \frac{n}{k} ⌋)

Explanation: Follows from $\sum_{d ∣ m}$ $μ$ (d) = [ $m = 1]$ . Grouping equal floor values lets this be evaluated in about O( $n^{2/3}$ ) using memoization.

Coprime pairs by Möbius

a = 1 \sum n b = 1 \sum n [g cd (a, b) = 1] = d = 1 \sum n μ (d) ⌊ \frac{n}{d} ⌋^{2}

Explanation: Group pairs by their gcd d and apply Möbius inversion. Useful to count primitive lattice points in a box.

Distinct floor values bound

# {⌊ n / i ⌋ : 1 \leq i \leq n} = O (n)

Explanation: The set of values taken by ⌊n/i⌋ has size about 2√n. This underlies the efficiency of block decomposition.

Triangular number

T (m) = i = 1 \sum m i = \frac{m ( m + 1 )}{2}

Explanation: Sum of the first m integers; appears in the $φ - s u m$ formula after Möbius inversion.

Complexity Analysis

The block decomposition for

S_{d}

(n) = ∑_{

i=1}^{n}

⌊n/i⌋ runs in O(√n) time and O(1) extra space. The reason is that q = ⌊n/i⌋ only changes O(√n) times, and we can jump i over maximal ranges [l, r] with the same q using r = ⌊n/q⌋. This reduces a length-n loop to about 2√n iterations. For

μ -

and

φ - re l a t e d

sums, direct sieving up to n is infeasible when n is large. Instead, we compute the Mertens function M(x) with a hybrid method: precompute μ up to a cutoff B using a linear sieve in O(B) time and space, forming M(x) for

x \leq B

by prefix sums; for

x > B

, use the recursion M(x) = 1 − ∑ M(⌊x/k⌋) grouped by equal floor values, with memoization. With B chosen around

x^{2/3}

, the total time is about O(

x^{2/3}

) and space O(B). In practice, similar performance is achievable with B between

x^{1/2}

and

x^{2/3}

, balancing memory and speed. Once M is available as a fast oracle for many x, sums like Φ(n) = ∑

μ (d)

T(⌊n/d⌋) and coprime-pair counts ∑

μ (d)

⌊n/d⌋^2 can be evaluated with an outer O(√n) block loop; each block needs O(1) evaluations of M at arguments roughly n/l, leading to overall O(

n^{2/3}

)–O(√n) time depending on B and hashing constants. Space usage is dominated by the sieve up to B and the memoization map of distinct floor-arguments, typically O(B + √n) entries, fitting well within memory for contest constraints.

Code Examples

O(√n) computation of S_d(n) = ∑_{i=1}^{n} d(i) via hyperbola (floor-division blocks)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes S_d(n) = sum_{k=1}^n d(k) using the identity S_d(n) = sum_{i=1}^n floor(n/i)
5 // Runs in O(sqrt(n)) time by grouping i where floor(n/i) is constant.
6 
7 long long sum_divisor_count(long long n) {
8     long long ans = 0;
9     for (long long l = 1, r; l <= n; l = r + 1) {
10         long long q = n / l;      // value of floor(n / i) on this block
11         r = n / q;                // maximal r with the same q
12         ans += (r - l + 1) * q;   // add q for each i in [l, r]
13     }
14     return ans;
15 }
16 
17 int main() {
18     ios::sync_with_stdio(false);
19     cin.tie(nullptr);
20 
21     long long n; 
22     if (!(cin >> n)) return 0;
23     cout << sum_divisor_count(n) << "\n";
24     return 0;
25 }
26

We use the lattice-points identity S_d(n) = ∑ ⌊n/i⌋ and the fact that ⌊n/i⌋ stays constant over ranges. For each block [l, r], we compute the common value q = ⌊n/l⌋ and jump r to ⌊n/q⌋, adding q times the block length.

Time: O(√n)Space: O(1)

Sublinear Mertens function M(n) with sieve + memoized floor-division recursion

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes M(n) = sum_{k=1}^n mu(k) sublinearly.
5 // Strategy: linear sieve up to B, build prefix M for x <= B; for x > B use
6 // recursion: M(x) = 1 - sum_{k=2}^x M(floor(x/k)), grouped by equal floor values.
7 // Choose B around n^{2/3} or sqrt(n) depending on memory.
8 
9 struct Mertens {
10     long long B;                      // sieve limit
11     vector<int> mu;                   // mu[0..B]
12     vector<long long> prefM;          // prefM[x] = sum_{i<=x} mu[i]
13     unordered_map<long long, long long> memo; // cache for x > B
14 
15     Mertens(long long n, long long B_hint = -1) {
16         if (B_hint == -1) {
17             // Heuristic: B ~ n^{2/3}, but cap to keep memory reasonable.
18             long double nd = (long double)n;
19             long long b = (long long)floor(powl(nd, 2.0L/3.0L));
20             const long long CAP = 20000000LL; // cap at 2e7 (~160MB for vectors of ints/long long)
21             B = min(b, CAP);
22         } else {
23             B = B_hint;
24         }
25         sieve_mu(B);
26     }
27 
28     void sieve_mu(long long N) {
29         mu.assign(N + 1, 0);
30         vector<int> primes;
31         vector<int> is_comp(N + 1, 0);
32         mu[1] = 1;
33         for (long long i = 2; i <= N; ++i) {
34             if (!is_comp[i]) {
35                 primes.push_back((int)i);
36                 mu[i] = -1;
37             }
38             for (int p : primes) {
39                 long long x = i * 1LL * p;
40                 if (x > N) break;
41                 is_comp[x] = 1;
42                 if (i % p == 0) { mu[x] = 0; break; }
43                 else mu[x] = -mu[i];
44             }
45         }
46         prefM.assign(N + 1, 0);
47         for (long long i = 1; i <= N; ++i) prefM[i] = prefM[i - 1] + mu[i];
48     }
49 
50     long long M(long long x) {
51         if (x <= B) return prefM[(size_t)x];
52         auto it = memo.find(x);
53         if (it != memo.end()) return it->second;
54         long long ans = 1; // since sum_{d|m} mu(d) = [m=1]
55         for (long long l = 2, r; l <= x; l = r + 1) {
56             long long q = x / l;     // q = floor(x / i)
57             r = x / q;               // maximal r with same q
58             ans -= (r - l + 1) * M(q);
59         }
60         memo.emplace(x, ans);
61         return ans;
62     }
63 };
64 
65 int main() {
66     ios::sync_with_stdio(false);
67     cin.tie(nullptr);
68 
69     long long n; if (!(cin >> n)) return 0;
70     // Build Mertens helper; you may tune the B_hint based on RAM/time.
71     Mertens mert(n);
72     cout << mert.M(n) << "\n";
73     return 0;
74 }
75

We precompute μ and its prefix up to B by a linear sieve; for larger x, we use the grouped recursion M(x) = 1 − ∑ M(⌊x/k⌋), caching results. The for-loop jumps over maximal ranges where ⌊x/i⌋ is constant, keeping the runtime near O(n^{2/3}).

Time: O(B) preprocessing and about O(n^{2/3}) query time for M(n), where B ≈ n^{2/3} (or √n in practice).Space: O(B) for sieve and O(√n) extra for memoized values.

Compute Φ(n) = ∑_{k=1}^{n} φ(k) using Möbius inversion and Mertens blocks

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Uses the identity: Phi(n) = sum_{d=1}^n mu(d) * T(floor(n/d)), where T(m)=m(m+1)/2.
5 // We group d where t = floor(n/d) is constant; the contribution from [l, r] is (M(r)-M(l-1)) * T(t).
6 
7 struct Mertens {
8     long long B; vector<int> mu; vector<long long> prefM; unordered_map<long long,long long> memo;
9     Mertens(long long n, long long B_hint = -1) {
10         if (B_hint == -1) {
11             long double nd = (long double)n;
12             long long b = (long long)floor(powl(nd, 2.0L/3.0L));
13             const long long CAP = 20000000LL;
14             B = min(b, CAP);
15         } else B = B_hint;
16         sieve_mu(B);
17     }
18     void sieve_mu(long long N) {
19         mu.assign(N+1, 0);
20         vector<int> primes; vector<int> is_comp(N+1, 0);
21         mu[1]=1; 
22         for (long long i=2;i<=N;++i){
23             if(!is_comp[i]){primes.push_back((int)i); mu[i]=-1;}
24             for(int p:primes){ long long x=i*1LL*p; if(x>N) break; is_comp[x]=1; if(i%p==0){ mu[x]=0; break;} else mu[x]=-mu[i]; }
25         }
26         prefM.assign(N+1,0); for(long long i=1;i<=N;++i) prefM[i]=prefM[i-1]+mu[i];
27     }
28     long long M(long long x){ if(x<=B) return prefM[(size_t)x]; auto it=memo.find(x); if(it!=memo.end()) return it->second; long long ans=1; for(long long l=2,r; l<=x; l=r+1){ long long q=x/l; r=x/q; ans -= (r-l+1)*M(q);} memo.emplace(x,ans); return ans; }
29 };
30 
31 static inline unsigned __int128 mul128(unsigned long long a, unsigned long long b){ return (unsigned __int128)a*b; }
32 
33 long long triangular(long long m){ return (__int128)m * (m + 1) / 2; }
34 
35 long long phi_prefix(long long n) {
36     Mertens mert(n);
37     long long ans = 0;
38     for (long long l = 1, r; l <= n; l = r + 1) {
39         long long t = n / l;     // t is constant on [l, r]
40         r = n / t;
41         long long sumMu = mert.M(r) - mert.M(l - 1);
42         long long Tt = triangular(t); // safe via 128-bit in helper
43         ans += (__int128)sumMu * Tt;  // widen to 128-bit to avoid overflow, then cast back
44     }
45     return ans;
46 }
47 
48 int main(){
49     ios::sync_with_stdio(false);
50     cin.tie(nullptr);
51 
52     long long n; if(!(cin>>n)) return 0;
53     cout << phi_prefix(n) << "\n";
54     return 0;
55 }
56

We apply Φ(n) = ∑ μ(d) T(⌊n/d⌋) and group d by equal floor values. Each block contributes (M(r) − M(l − 1)) times the triangular number of t. The Mertens helper provides fast M(x) for needed x, making the total sublinear. Intermediate products use 128-bit to avoid overflow.

Time: Approximately O(n^{2/3}) with a suitable sieve cutoff and memoization.Space: O(B) for the sieve and O(√n) for memoized M(x) values.

Count coprime pairs in [1..n]^2 via μ and block decomposition

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Counts pairs (a,b) with 1<=a,b<=n and gcd(a,b)=1 using sum_{d=1}^n mu(d) * floor(n/d)^2.
5 // Group d where t=floor(n/d) is constant; contribution is (M(r)-M(l-1)) * t^2.
6 
7 struct Mertens {
8     long long B; vector<int> mu; vector<long long> prefM; unordered_map<long long,long long> memo;
9     Mertens(long long n, long long B_hint = -1){
10         if(B_hint==-1){ long double nd=(long double)n; long long b=(long long)floor(powl(nd, 2.0L/3.0L)); const long long CAP=20000000LL; B=min(b,CAP);} else B=B_hint; sieve_mu(B);
11     }
12     void sieve_mu(long long N){ mu.assign(N+1,0); vector<int> primes; vector<int> is_comp(N+1,0); mu[1]=1; for(long long i=2;i<=N;++i){ if(!is_comp[i]){primes.push_back((int)i); mu[i]=-1;} for(int p:primes){ long long x=i*1LL*p; if(x>N) break; is_comp[x]=1; if(i%p==0){ mu[x]=0; break;} else mu[x]=-mu[i]; } } prefM.assign(N+1,0); for(long long i=1;i<=N;++i) prefM[i]=prefM[i-1]+mu[i]; }
13     long long M(long long x){ if(x<=B) return prefM[(size_t)x]; auto it=memo.find(x); if(it!=memo.end()) return it->second; long long ans=1; for(long long l=2,r; l<=x; l=r+1){ long long q=x/l; r=x/q; ans -= (r-l+1)*M(q);} memo.emplace(x,ans); return ans; }
14 };
15 
16 unsigned __int128 sq128(unsigned long long x){ return (unsigned __int128)x * x; }
17 
18 unsigned long long coprime_pairs(long long n){
19     Mertens mert(n);
20     unsigned __int128 ans = 0;
21     for(long long l=1,r; l<=n; l=r+1){
22         long long t = n / l;
23         r = n / t;
24         long long sumMu = mert.M(r) - mert.M(l-1);
25         ans += (unsigned __int128)sumMu * (unsigned __int128)t * (unsigned __int128)t;
26     }
27     return (unsigned long long)ans; // fits in 64-bit for n up to around 1e9; cast carefully for larger n
28 }
29 
30 int main(){
31     ios::sync_with_stdio(false);
32     cin.tie(nullptr);
33 
34     long long n; if(!(cin>>n)) return 0;
35     cout << coprime_pairs(n) << "\n";
36     return 0;
37 }
38

We use the identity ∑_{a,b ≤ n} [gcd(a, b) = 1] = ∑_{d=1}^{n} μ(d) ⌊n/d⌋^2 and block over d. The Mertens helper provides the range sums of μ via M(r) − M(l − 1). We compute t^2 in 128-bit to avoid overflow.

Time: Approximately O(n^{2/3}) with the hybrid Mertens method.Space: O(B) for the sieve plus O(√n) cached values.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes S_d(n) = sum_{k=1}^n d(k) using the identity S_d(n) = sum_{i=1}^n floor(n/i)
5	// Runs in O(sqrt(n)) time by grouping i where floor(n/i) is constant.
6
7	long long sum_divisor_count(long long n) {
8	long long ans = 0;
9	for (long long l = 1, r; l <= n; l = r + 1) {
10	long long q = n / l; // value of floor(n / i) on this block
11	r = n / q; // maximal r with the same q
12	ans += (r - l + 1) * q; // add q for each i in [l, r]
13	}
14	return ans;
15	}
16
17	int main() {
18	ios::sync_with_stdio(false);
19	cin.tie(nullptr);
20
21	long long n;
22	if (!(cin >> n)) return 0;
23	cout << sum_divisor_count(n) << "\n";
24	return 0;
25	}
26

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes M(n) = sum_{k=1}^n mu(k) sublinearly.
5	// Strategy: linear sieve up to B, build prefix M for x <= B; for x > B use
6	// recursion: M(x) = 1 - sum_{k=2}^x M(floor(x/k)), grouped by equal floor values.
7	// Choose B around n^{2/3} or sqrt(n) depending on memory.
8
9	struct Mertens {
10	long long B; // sieve limit
11	vector<int> mu; // mu[0..B]
12	vector<long long> prefM; // prefM[x] = sum_{i<=x} mu[i]
13	unordered_map<long long, long long> memo; // cache for x > B
14
15	Mertens(long long n, long long B_hint = -1) {
16	if (B_hint == -1) {
17	// Heuristic: B ~ n^{2/3}, but cap to keep memory reasonable.
18	long double nd = (long double)n;
19	long long b = (long long)floor(powl(nd, 2.0L/3.0L));
20	const long long CAP = 20000000LL; // cap at 2e7 (~160MB for vectors of ints/long long)
21	B = min(b, CAP);
22	} else {
23	B = B_hint;
24	}
25	sieve_mu(B);
26	}
27
28	void sieve_mu(long long N) {
29	mu.assign(N + 1, 0);
30	vector<int> primes;
31	vector<int> is_comp(N + 1, 0);
32	mu[1] = 1;
33	for (long long i = 2; i <= N; ++i) {
34	if (!is_comp[i]) {
35	primes.push_back((int)i);
36	mu[i] = -1;
37	}
38	for (int p : primes) {
39	long long x = i * 1LL * p;
40	if (x > N) break;
41	is_comp[x] = 1;
42	if (i % p == 0) { mu[x] = 0; break; }
43	else mu[x] = -mu[i];
44	}
45	}
46	prefM.assign(N + 1, 0);
47	for (long long i = 1; i <= N; ++i) prefM[i] = prefM[i - 1] + mu[i];
48	}
49
50	long long M(long long x) {
51	if (x <= B) return prefM[(size_t)x];
52	auto it = memo.find(x);
53	if (it != memo.end()) return it->second;
54	long long ans = 1; // since sum_{d\|m} mu(d) = [m=1]
55	for (long long l = 2, r; l <= x; l = r + 1) {
56	long long q = x / l; // q = floor(x / i)
57	r = x / q; // maximal r with same q
58	ans -= (r - l + 1) * M(q);
59	}
60	memo.emplace(x, ans);
61	return ans;
62	}
63	};
64
65	int main() {
66	ios::sync_with_stdio(false);
67	cin.tie(nullptr);
68
69	long long n; if (!(cin >> n)) return 0;
70	// Build Mertens helper; you may tune the B_hint based on RAM/time.
71	Mertens mert(n);
72	cout << mert.M(n) << "\n";
73	return 0;
74	}
75

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Uses the identity: Phi(n) = sum_{d=1}^n mu(d) * T(floor(n/d)), where T(m)=m(m+1)/2.
5	// We group d where t = floor(n/d) is constant; the contribution from [l, r] is (M(r)-M(l-1)) * T(t).
6
7	struct Mertens {
8	long long B; vector<int> mu; vector<long long> prefM; unordered_map<long long,long long> memo;
9	Mertens(long long n, long long B_hint = -1) {
10	if (B_hint == -1) {
11	long double nd = (long double)n;
12	long long b = (long long)floor(powl(nd, 2.0L/3.0L));
13	const long long CAP = 20000000LL;
14	B = min(b, CAP);
15	} else B = B_hint;
16	sieve_mu(B);
17	}
18	void sieve_mu(long long N) {
19	mu.assign(N+1, 0);
20	vector<int> primes; vector<int> is_comp(N+1, 0);
21	mu[1]=1;
22	for (long long i=2;i<=N;++i){
23	if(!is_comp[i]){primes.push_back((int)i); mu[i]=-1;}
24	for(int p:primes){ long long x=i1LLp; if(x>N) break; is_comp[x]=1; if(i%p==0){ mu[x]=0; break;} else mu[x]=-mu[i]; }
25	}
26	prefM.assign(N+1,0); for(long long i=1;i<=N;++i) prefM[i]=prefM[i-1]+mu[i];
27	}
28	long long M(long long x){ if(x<=B) return prefM[(size_t)x]; auto it=memo.find(x); if(it!=memo.end()) return it->second; long long ans=1; for(long long l=2,r; l<=x; l=r+1){ long long q=x/l; r=x/q; ans -= (r-l+1)*M(q);} memo.emplace(x,ans); return ans; }
29	};
30
31	static inline unsigned __int128 mul128(unsigned long long a, unsigned long long b){ return (unsigned __int128)a*b; }
32
33	long long triangular(long long m){ return (__int128)m * (m + 1) / 2; }
34
35	long long phi_prefix(long long n) {
36	Mertens mert(n);
37	long long ans = 0;
38	for (long long l = 1, r; l <= n; l = r + 1) {
39	long long t = n / l; // t is constant on [l, r]
40	r = n / t;
41	long long sumMu = mert.M(r) - mert.M(l - 1);
42	long long Tt = triangular(t); // safe via 128-bit in helper
43	ans += (__int128)sumMu * Tt; // widen to 128-bit to avoid overflow, then cast back
44	}
45	return ans;
46	}
47
48	int main(){
49	ios::sync_with_stdio(false);
50	cin.tie(nullptr);
51
52	long long n; if(!(cin>>n)) return 0;
53	cout << phi_prefix(n) << "\n";
54	return 0;
55	}
56

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Counts pairs (a,b) with 1<=a,b<=n and gcd(a,b)=1 using sum_{d=1}^n mu(d) * floor(n/d)^2.
5	// Group d where t=floor(n/d) is constant; contribution is (M(r)-M(l-1)) * t^2.
6
7	struct Mertens {
8	long long B; vector<int> mu; vector<long long> prefM; unordered_map<long long,long long> memo;
9	Mertens(long long n, long long B_hint = -1){
10	if(B_hint==-1){ long double nd=(long double)n; long long b=(long long)floor(powl(nd, 2.0L/3.0L)); const long long CAP=20000000LL; B=min(b,CAP);} else B=B_hint; sieve_mu(B);
11	}
12	void sieve_mu(long long N){ mu.assign(N+1,0); vector<int> primes; vector<int> is_comp(N+1,0); mu[1]=1; for(long long i=2;i<=N;++i){ if(!is_comp[i]){primes.push_back((int)i); mu[i]=-1;} for(int p:primes){ long long x=i1LLp; if(x>N) break; is_comp[x]=1; if(i%p==0){ mu[x]=0; break;} else mu[x]=-mu[i]; } } prefM.assign(N+1,0); for(long long i=1;i<=N;++i) prefM[i]=prefM[i-1]+mu[i]; }
13	long long M(long long x){ if(x<=B) return prefM[(size_t)x]; auto it=memo.find(x); if(it!=memo.end()) return it->second; long long ans=1; for(long long l=2,r; l<=x; l=r+1){ long long q=x/l; r=x/q; ans -= (r-l+1)*M(q);} memo.emplace(x,ans); return ans; }
14	};
15
16	unsigned __int128 sq128(unsigned long long x){ return (unsigned __int128)x * x; }
17
18	unsigned long long coprime_pairs(long long n){
19	Mertens mert(n);
20	unsigned __int128 ans = 0;
21	for(long long l=1,r; l<=n; l=r+1){
22	long long t = n / l;
23	r = n / t;
24	long long sumMu = mert.M(r) - mert.M(l-1);
25	ans += (unsigned __int128)sumMu * (unsigned __int128)t * (unsigned __int128)t;
26	}
27	return (unsigned long long)ans; // fits in 64-bit for n up to around 1e9; cast carefully for larger n
28	}
29
30	int main(){
31	ios::sync_with_stdio(false);
32	cin.tie(nullptr);
33
34	long long n; if(!(cin>>n)) return 0;
35	cout << coprime_pairs(n) << "\n";
36	return 0;
37	}
38