Problem 355: Maximal Coprime Subset

Solution

Key Observations

1. Pairwise coprime subset: In a pairwise coprime subset, at most one element can be divisible by any given prime $p$.

2. Greedy strategy: For each prime $p \le n$, we can include at most one multiple of $p$. To maximize the sum, we want the largest multiple of each prime, but we must ensure consistency (no element is “used” for two different primes in a conflicting way).

3. Structure of optimal subset: The optimal subset of $\{1, \ldots, n\}$ consists of:

   • 1 (always included, coprime to everything)
   • For each prime $p \le n$, at most one multiple of $p$
   • The elements chosen must be pairwise coprime

Editorial

The problem reduces to: for each $n$, find a maximum-weight independent set in a conflict graph. This can be solved using the following approach. So. We always include 1. We then iterate over each prime $p \le n$, the “best representative” is $p$ itself (or the largest power of $p$ that is $\le n$), since prime powers are coprime to numbers not divisible by $p$. Finally, more precisely: include each prime $p$ with $n/2 < p \le n$ (these are large primes whose only multiple in range is themselves).

Pseudocode

Always include 1
For each prime $p \le n$, the "best representative" is $p$ itself (or the largest power of $p$ that is $\le n$), since prime powers are coprime to numbers not divisible by $p$
More precisely: include each prime $p$ with $n/2 < p \le n$ (these are large primes whose only multiple in range is themselves)
For smaller primes, choose the largest prime power $p^k \le n$

Final Computation

This can be computed efficiently by iterating over primes and their powers.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Answer

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

/*
 * Problem 355: Maximal Coprime Subset
 *
 * S(n) = 1 + sum over primes p <= n of p^floor(log_p(n))
 *
 * We need sum_{n=1}^{N} S(n).
 *
 * For each prime p and exponent k, p^k contributes to S(n) for n in [p^k, p^{k+1}-1].
 * Specifically, for n >= p, the contribution of prime p is the largest p^a <= n.
 *
 * sum_{n=1}^{N} S(n) = N (from the 1's) +
 *   sum over primes p <= N, sum over k>=1 where p^k <= N:
 *     p^k * (min(p^{k+1}-1, N) - p^k + 1)
 *   + sum over primes p <= N:
 *     p * (min(p^2-1, N) - p + 1)  [k=1 contribution, but p^1 = p contributes for n in [p, p^2-1]]
 *
 * Wait, let me reconsider. For each prime p <= N:
 *   For n in [p, p^2-1] (if p^2-1 <= N, else [p, N]): contribution is p
 *   For n in [p^2, p^3-1]: contribution is p^2
 *   ...
 *   For n in [p^k, min(p^{k+1}-1, N)]: contribution is p^k
 *
 * Total contribution of prime p:
 *   sum_{k=1}^{...} p^k * (min(p^{k+1}-1, N) - p^k + 1)
 */

int main() {
    const long long N = 100000; // 10^5

    // Sieve primes up to N
    vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (long long i = 2; i <= N; i++) {
        if (is_prime[i]) {
            for (long long j = i * i; j <= N; j += i)
                is_prime[j] = false;
        }
    }

    long long total = N; // contribution of 1 for each n from 1 to N

    for (long long p = 2; p <= N; p++) {
        if (!is_prime[p]) continue;

        long long pk = p; // p^k, starting with k=1
        while (pk <= N) {
            long long next_pk = pk * p; // p^{k+1}
            long long upper;
            if (next_pk - 1 <= N && next_pk > pk) { // check no overflow
                upper = next_pk - 1;
            } else {
                upper = N;
            }
            // pk contributes for n in [pk, upper]
            long long count = upper - pk + 1;
            total += pk * count;

            if (pk > N / p) break; // prevent overflow
            pk *= p;
        }
    }

    cout << total << endl;

    return 0;
}

"""
Problem 355: Maximal Coprime Subset

S(n) = 1 + sum over primes p <= n of p^floor(log_p(n))

The maximum-sum pairwise coprime subset of {1,...,n} is {1} union
{p^floor(log_p(n)) for each prime p <= n}.

We compute sum_{n=1}^{N} S(n) where N = 10^5.

For each prime p and power k, p^k contributes to S(n) for
n in [p^k, min(p^{k+1}-1, N)].
"""

def solve():
    N = 100000  # 10^5

    # Sieve of Eratosthenes
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(N**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, N + 1, i):
                is_prime[j] = False

    total = N  # contribution of 1 for each n

    for p in range(2, N + 1):
        if not is_prime[p]:
            continue

        pk = p  # p^k, k=1
        while pk <= N:
            next_pk = pk * p  # p^{k+1}
            if next_pk - 1 <= N and next_pk > pk:
                upper = next_pk - 1
            else:
                upper = N

            count = upper - pk + 1
            total += pk * count

            if pk > N // p:
                break
            pk *= p

    print(total)

if __name__ == "__main__":
    solve()