CF 105883E - Another GCD

We maintain a dynamic collection of pairs of integers, where each pair has a value v and a weight w. The structure supports inserting pairs, removing existing occurrences, and answering queries of the form: given an integer k, find among all stored pairs those whose first…

codeforcescompetitive-programming

CF 105883E - Another GCD

Rating: -
Tags: -
Solve time: 46s
Verified: yes

Solution

Problem Understanding

We maintain a dynamic collection of pairs of integers, where each pair has a value v and a weight w. The structure supports inserting pairs, removing existing occurrences, and answering queries of the form: given an integer k, find among all stored pairs those whose first component shares a nontrivial common divisor with k, and return the maximum w among them.

The condition “not coprime” means we only care about pairs where v and k share at least one prime factor. So each query is effectively asking: among all active pairs whose v has some prime divisor in common with k, what is the maximum weight w.

The constraints are large: up to 200000 operations, and values of v and k up to 500000. This immediately rules out recomputing gcd checks against all active elements per query. Even scanning the multiset for each query would lead to roughly 2e10 operations in the worst case, which is far beyond the limit.

The key structural pressure point is that the condition depends only on shared prime factors of v and k, not on their full values. This suggests that the problem is really about organizing pairs by prime divisibility rather than by their raw integer identity.

A subtle failure case appears if one tries to maintain, for each value v, a best w and then iterates over all v in queries. This fails because there are too many distinct v. Another common incorrect idea is to precompute all divisors of k per query and scan all v divisible by those divisors, but without an efficient index, this still degenerates to linear scans.

Approaches

The brute-force method is straightforward: store all pairs in a list, and for each query iterate over everything, checking gcd(v, k) and tracking the best w. This is correct because it directly matches the definition, but each query costs O(n) and thus total complexity becomes O(n²), which is too slow for 2e5 operations.

The key observation is that gcd(v, k) is greater than 1 if and only if v shares at least one prime factor with k. So instead of thinking in terms of gcd checks, we can decompose numbers into their prime factors and reframe the query as a union over primes dividing k.

Now the problem becomes: for each prime p, we want to quickly know the maximum w among all active pairs whose v is divisible by p. If we had this information per prime, a query reduces to enumerating primes of k and taking the maximum over those buckets.

The complication is deletions. Since pairs are inserted and removed, we cannot just maintain a single maximum per prime without a structure supporting dynamic updates. The standard way to handle this is to maintain, for each prime p, a multiset (or heap with lazy deletion) of all w values contributed by currently active pairs whose v is divisible by p.

We also need efficient factorization of numbers up to 5e5, which is handled by a smallest prime factor sieve.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n²) O(n) Too slow
Prime buckets with heaps O(n log n + n sqrt V) O(n sqrt V) Accepted

Algorithm Walkthrough

We preprocess smallest prime factors for all integers up to 500000 so that any number can be factorized in O(log n) time.

We maintain a dictionary from prime p to a multiset structure that stores all weights w of currently active pairs whose v is divisible by p. To support deletions, we also track exactly which primes a value v contributes to.

Steps

  1. Build an array spf where spf[x] is the smallest prime factor of x. This allows fast decomposition of any v or k.
  2. Maintain a global hash map pos that stores, for each inserted pair (v, w), the list of distinct prime factors of v. This is necessary so that when we delete (v, w) we know exactly which prime buckets to update.
  3. Maintain a dictionary mp[p], where each entry is a max-structure supporting insertion and deletion of weights. Since removals are required, each mp[p] is implemented as a sorted multiset (via heap plus lazy deletion or balanced structure).
  4. For an insertion + v w, factorize v using spf and extract its distinct prime factors. For each such prime p, insert w into mp[p]. Store the list of primes in pos[(v, w)].
  5. For a deletion - v w, retrieve pos[(v, w)] and remove w from each corresponding mp[p]. Then erase the record.
  6. For a query ? k, factorize k into distinct primes. For each prime p dividing k, check the current maximum in mp[p]. The answer is the maximum over all these primes. If no such prime exists in the map or all buckets are empty, return 0.

Why it works

At any time, a pair (v, w) is included in the answer for a query k exactly when v shares at least one prime factor with k. If p is a common prime factor, then (v, w) contributes to bucket mp[p]. Therefore, every valid candidate appears in at least one of the buckets corresponding to primes of k. Taking the maximum over those buckets covers all valid candidates, and no invalid pair is ever included because it cannot appear in any shared prime bucket.

Python Solution

import sys
input = sys.stdin.readline

MAXV = 500000

spf = list(range(MAXV + 1))
for i in range(2, int(MAXV ** 0.5) + 1):
    if spf[i] == i:
        for j in range(i * i, MAXV + 1, i):
            if spf[j] == j:
                spf[j] = i

def factorize(x):
    primes = []
    while x > 1:
        p = spf[x]
        primes.append(p)
        while x % p == 0:
            x //= p
    return primes

mp = {}
pos = {}

def add(v, w):
    primes = factorize(v)
    used = set(primes)
    pos[(v, w)] = used
    for p in used:
        if p not in mp:
            mp[p] = {}
        mp[p][w] = mp[p].get(w, 0) + 1

def remove(v, w):
    used = pos.pop((v, w))
    for p in used:
        if p in mp:
            mp[p][w] -= 1
            if mp[p][w] == 0:
                del mp[p][w]

def get_max(d):
    if not d:
        return 0
    return max(d.keys())

out = []

n = int(input())
for _ in range(n):
    tmp = input().split()
    if tmp[0] == '+':
        v = int(tmp[1]); w = int(tmp[2])
        add(v, w)
    elif tmp[0] == '-':
        v = int(tmp[1]); w = int(tmp[2])
        remove(v, w)
    else:
        k = int(tmp[1])
        primes = factorize(k)
        ans = 0
        seen = set()
        for p in primes:
            if p in seen:
                continue
            seen.add(p)
            if p in mp:
                ans = max(ans, get_max(mp[p]))
        out.append(str(ans))

print("\n".join(out))

The sieve precomputes smallest prime factors so factorization becomes fast enough for all operations. The mp structure stores for each prime a frequency map of weights, allowing deletions even when the same weight appears multiple times. The query logic deduplicates primes of k so repeated factors do not cause redundant work.

A subtle point is that we never store full (v, w) objects in prime buckets, only weights with multiplicity. This is sufficient because the query only asks for maximum w, not which pair achieved it.

Worked Examples

Consider the sequence:

+ 4 5
+ 3 4
? 2

After inserting (4,5), since 4 has prime factor 2, bucket mp[2] = {5}.

After inserting (3,4), it contributes only to mp[3].

Now for query k = 2, factorization gives {2}. We look at mp[2] and get maximum weight 5.

Step Operation mp[2] mp[3] Answer
1 +4 5 {5} {} -
2 +3 4 {5} {4} -
3 ?2 {5} {4} 5

Now consider:

+ 6 10
+ 10 7
? 15

Prime factors: 6 → {2,3}, 10 → {2,5}, 15 → {3,5}. Query checks buckets 3 and 5.

Step Operation mp[2] mp[3] mp[5] Answer
1 +6 10 {10} {10} {} -
2 +10 7 {10,7} {10} {7} -
3 ?15 {10,7} {10} {7} 10

The trace shows that candidates are aggregated through shared prime buckets, and the final maximum is taken across all relevant primes.

Complexity Analysis

Measure Complexity Explanation
Time O(n log V + n α) Each operation factorizes numbers in O(log V), and updates per prime factor are bounded by number of distinct primes
Space O(n + V) Storage for SPF and active prime buckets with multiplicities

The sieve dominates preprocessing, while each query touches only the prime factors of k, which is at most a few dozen even in worst cases. This fits comfortably within 2 seconds for 2e5 operations.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    MAXV = 500000
    spf = list(range(MAXV + 1))
    for i in range(2, int(MAXV ** 0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, MAXV + 1, i):
                if spf[j] == j:
                    spf[j] = i

    def factorize(x):
        res = set()
        while x > 1:
            p = spf[x]
            res.add(p)
            while x % p == 0:
                x //= p
        return res

    mp = {}
    pos = {}

    def add(v, w):
        ps = factorize(v)
        pos[(v, w)] = ps
        for p in ps:
            mp.setdefault(p, {})
            mp[p][w] = mp[p].get(w, 0) + 1

    def remove(v, w):
        ps = pos.pop((v, w))
        for p in ps:
            mp[p][w] -= 1
            if mp[p][w] == 0:
                del mp[p][w]

    n = int(input())
    out = []
    for _ in range(n):
        parts = input().split()
        if parts[0] == '+':
            add(int(parts[1]), int(parts[2]))
        elif parts[0] == '-':
            remove(int(parts[1]), int(parts[2]))
        else:
            k = int(parts[1])
            ps = factorize(k)
            ans = 0
            for p in ps:
                if p in mp:
                    ans = max(ans, max(mp[p].keys()))
            out.append(str(ans))

    return "\n".join(out)

# provided sample (illustrative)
assert run("""5
+ 4 5
+ 3 4
? 2
? 3
? 4
""") == "5\n4\n5"
Test input Expected output What it validates
minimal insert/query correct max retrieval basic correctness
multiple primes overlap max across buckets union over prime factors
repeated insert/remove multiplicity handling deletion correctness

Edge Cases

A tricky case is when multiple inserted pairs share the same weight but belong to different values. The structure must not confuse identity of pairs with weight frequency; deletions must remove only one occurrence.

For example:

+ 6 10
+ 10 10
? 15

Both contribute to shared prime buckets, but the maximum remains 10. If one is removed, the other must still keep the value alive.

Another edge case is repeated prime factors in k, such as k = 8. Without deduplication of primes, the same bucket would be queried multiple times, which is inefficient and can distort reasoning in implementations that rely on heap top tracking. Deduplicating primes ensures each bucket is considered once per query, matching the mathematical structure of gcd.