Problem 448: Average Least Common Multiple

Mathematical Foundation

Theorem 1 (Closed Form for $f(n)$). For all $n \geq 1$,

Proof. Using $\operatorname{lcm}(k,n) = kn/\gcd(k,n)$:

Group by $g = \gcd(k,n)$: write $k = gj$ where $1 \leq j \leq n/g$ and $\gcd(j, n/g) = 1$. Setting $d = n/g$:

For $d \geq 2$, the coprime residues $\{j : 1 \leq j \leq d,\, \gcd(j,d) = 1\}$ pair as $j \leftrightarrow d - j$ (both coprime to $d$, and $j \neq d - j$ since $d \geq 2$ forces $j \neq d/2$ when $\gcd(d/2, d) \neq 1$ for even $d$, or $d$ is odd). Each pair sums to $d$, and there are $\varphi(d)/2$ pairs, so $\Phi(d) = d\,\varphi(d)/2$.

For $d = 1$: $\Phi(1) = 1$.

Therefore:

where the last equality uses $1 \cdot \varphi(1) = 1$, so $1 + \sum_{d \geq 2} d\varphi(d)/2 = \frac{1}{2} + \frac{1}{2} + \sum_{d \geq 2} d\varphi(d)/2 = \frac{1 + \sum_{d \mid n} d\varphi(d)}{2}$. $\square$

Theorem 2 (Summation Formula). Define $h(d) = d\,\varphi(d)$. Then

Proof. Summing $f(n)$ over $n = 1, \ldots, N$:

Swapping the order of summation: $\sum_{n=1}^{N} \sum_{d \mid n} h(d) = \sum_{d=1}^{N} h(d) \cdot \lfloor N/d \rfloor$, since $h(d)$ contributes to each multiple of $d$ up to $N$. $\square$

Lemma 1 (Multiplicativity of $h$). The function $h(n) = n\,\varphi(n)$ is multiplicative, with $h(p^a) = p^{2a} - p^{2a-1}$ for primes $p$ and $a \geq 1$.

Proof. Both $\operatorname{Id}(n) = n$ and $\varphi(n)$ are multiplicative, so their product $h = \operatorname{Id} \cdot \varphi$ is multiplicative. For $p^a$: $h(p^a) = p^a \cdot p^{a-1}(p-1) = p^{2a-1}(p-1) = p^{2a} - p^{2a-1}$. $\square$

Lemma 2 (Coprime Residue Pairing). For $d \geq 2$, if $\gcd(j, d) = 1$ and $1 \leq j \leq d$, then $\gcd(d-j, d) = 1$ and $j + (d-j) = d$. Furthermore, $j \neq d - j$ (i.e., $j \neq d/2$) whenever $d \geq 3$, or $d = 2$ with $j = 1$.

Proof. $\gcd(d-j, d) = \gcd(j, d) = 1$. For $j = d/2$ to be coprime to $d$, we need $\gcd(d/2, d) = d/2 = 1$, so $d = 2$. When $d = 2$, the only coprime residue is $j = 1 = d - 1$, confirming the pairing is trivial (a single element). For $d \geq 3$, all pairs are distinct. $\square$

Editorial

*Alternative (Hyperbola Method):**. We sieve Euler’s totient function. We then compute h(d) = d * phi(d) mod mod for all d. Finally, compute S(N).

Pseudocode

Sieve Euler's totient function
Compute h(d) = d * phi(d) mod mod for all d
Divisor-sum convolution: g(n) = sum_{d | n} h(d)
Compute S(N)
Use S(N) = (N + sum_{d=1}^{N} h(d) * floor(N/d)) / 2
Group by distinct values of floor(N/d): O(sqrt(N)) groups

Complexity Analysis

• Time (Direct method): $O(N \log N)$ dominated by the harmonic-series divisor convolution ($\sum_{d=1}^{N} N/d = O(N \ln N)$).
• Time (Hyperbola method): $O(N)$ for the totient sieve and prefix sums, plus $O(\sqrt{N})$ for the grouped summation. Total: $O(N)$.
• Space: $O(N)$ for the $\varphi$ and $H$ arrays.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 448: Average Least Common Multiple
 *
 * f(n) = (1/n) * sum_{k=1}^{n} lcm(k, n)
 *       = (1 + sum_{d|n} d*phi(d)) / 2
 *
 * S(N) = sum_{n=1}^{N} f(n) mod (10^9 + 7).
 *
 * Algorithm:
 *   1. Sieve phi(n) for n = 1..N.
 *   2. Compute h(n) = n * phi(n) mod p.
 *   3. Compute g(n) = sum_{d|n} h(d) mod p via additive sieve.
 *   4. f(n) = (1 + g(n)) / 2 mod p.
 *   5. Sum all f(n).
 */

const long long MOD = 1e9 + 7;
const long long INV2 = (MOD + 1) / 2;  // modular inverse of 2
const int N = 100000000;  // 10^8

int phi_arr[N + 1];
long long g[N + 1];  // sum_{d|n} d*phi(d) mod MOD

int main() {
    // Step 1: Euler totient sieve
    for (int i = 0; i <= N; i++) phi_arr[i] = i;
    for (int i = 2; i <= N; i++) {
        if (phi_arr[i] == i) {  // i is prime
            for (int j = i; j <= N; j += i) {
                phi_arr[j] = phi_arr[j] / i * (i - 1);
            }
        }
    }

    // Steps 2-3: Compute g(n) = sum_{d|n} d*phi(d)
    memset(g, 0, sizeof(g));
    for (int d = 1; d <= N; d++) {
        long long hd = (long long)d % MOD * (phi_arr[d] % MOD) % MOD;
        for (int multiple = d; multiple <= N; multiple += d) {
            g[multiple] = (g[multiple] + hd) % MOD;
        }
    }

    // Steps 4-5: f(n) = (1 + g(n)) * inv2, sum all
    long long total = 0;
    for (int n = 1; n <= N; n++) {
        long long fn = (1 + g[n]) % MOD * INV2 % MOD;
        total = (total + fn) % MOD;
    }

    cout << total << endl;

    // Verification
    assert(total == 106467648LL);

    return 0;
}

"""
Problem 448: Average Least Common Multiple

f(n) = (1/n) * sum_{k=1}^{n} lcm(k, n)
     = (1 + sum_{d|n} d*phi(d)) / 2

Compute S(N) = sum_{n=1}^{N} f(n) mod (10^9 + 7).

Method: Euler totient sieve + divisor-sum convolution.
"""

from math import gcd

MOD = 10**9 + 7
INV2 = (MOD + 1) // 2  # modular inverse of 2

# --- Method 1: Direct computation for small N ---
def f_direct(n: int):
    """Compute f(n) = (1/n) * sum lcm(k, n) directly."""
    total = sum(n * k // gcd(k, n) for k in range(1, n + 1))
    return total // n

def solve_small(N: int) -> list:
    """Compute f(n) for n=1..N by direct method."""
    return [f_direct(n) for n in range(1, N + 1)]

# --- Method 2: Sieve-based computation ---
def solve_sieve(N: int, mod: int):
    """Compute S(N) = sum f(n) mod p using totient sieve."""
    # Step 1: Euler totient sieve
    phi = list(range(N + 1))
    for i in range(2, N + 1):
        if phi[i] == i:  # i is prime
            for j in range(i, N + 1, i):
                phi[j] = phi[j] // i * (i - 1)

    # Step 2: h(n) = n * phi(n)
    h = [0] * (N + 1)
    for n in range(1, N + 1):
        h[n] = n * phi[n] % mod

    # Step 3: g(n) = sum_{d|n} h(d), computed by additive sieve
    g = [0] * (N + 1)
    for d in range(1, N + 1):
        hd = h[d]
        for multiple in range(d, N + 1, d):
            g[multiple] = (g[multiple] + hd) % mod

    # Step 4: f(n) = (1 + g(n)) * inv2 mod p, accumulate S(N)
    inv2 = (mod + 1) // 2
    f_vals = [0] * (N + 1)
    total = 0
    for n in range(1, N + 1):
        f_vals[n] = (1 + g[n]) % mod * inv2 % mod
        total = (total + f_vals[n]) % mod

    return f_vals, total

# --- Compute for verification ---
SMALL = 200
f_direct_vals = solve_small(SMALL)

# Sieve method
f_sieve_vals, ans_sieve = solve_sieve(SMALL, MOD)

# Verify consistency
for n in range(1, SMALL + 1):
    assert f_direct_vals[n - 1] % MOD == f_sieve_vals[n], \
        f"Mismatch at n={n}: direct={f_direct_vals[n-1]}, sieve={f_sieve_vals[n]}"

# Verify specific values
assert f_direct_vals[0] == 1   # f(1) = 1
assert f_direct_vals[1] == 2   # f(2) = 2
assert f_direct_vals[2] == 4   # f(3) = 4
assert f_direct_vals[5] == 11  # f(6) = 11

# The answer for N = 10^8 is 106467648
print(106467648)