CF 104308E - Unwanted Divisors Again

We are given an integer $m$ and an array $a$. The task is to look at every divisor $d$ of $m$, and decide whether $d$ is “safe” or “bad”. A divisor $d$ is considered bad if there exists at least one array element $ai$ such that $d$ divides $ai$. Otherwise, $d$ is safe.

codeforcescompetitive-programming

CF 104308E - Unwanted Divisors Again

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

Solution

Problem Understanding

We are given an integer $m$ and an array $a$. The task is to look at every divisor $d$ of $m$, and decide whether $d$ is “safe” or “bad”. A divisor $d$ is considered bad if there exists at least one array element $a_i$ such that $d$ divides $a_i$. Otherwise, $d$ is safe. The goal is to count how many divisors of $m$ are safe.

Another way to see the condition is that we are filtering divisors of $m$ by excluding those that appear as a divisor of at least one array element. We are not interested in which element triggers the exclusion, only whether it happens at least once.

The constraints push us toward careful factorization reasoning. The sum of $n$ over all test cases can reach $10^6$, and $m$ is up to $10^9$. That immediately rules out any solution that tries to check every divisor of $m$ against every array element directly. Even iterating over all pairs would be far too slow.

A second subtle issue is that the same divisor of $m$ might appear in many array elements. A naive approach that recomputes divisibility per element per divisor would repeatedly waste work.

A typical pitfall appears when $m$ is small but the array is large. For example, if $m = 1$, the only divisor is $1$, and the answer depends only on whether any $a_i$ equals $0$ or $1$ in divisibility terms. A careless implementation that assumes multiple divisors or forgets the special structure of $m$ can easily miscount.

Another edge case occurs when many array elements are multiples of a small divisor of $m$. For instance, if $m = 12$ and the array contains many multiples of $2$, then divisor $2$ should be excluded even if it never appears explicitly in the array. The logic depends on divisibility propagation, not equality.

Approaches

The brute-force perspective starts naturally by enumerating all divisors of $m$. Since $m \le 10^9$, the number of divisors is at most around a few thousand. For each divisor $d$, we then scan the entire array and check whether there exists any $a_i$ such that $a_i \bmod d = 0$. If none exist, we count it.

This works because the definition is directly checked. However, its cost is $O(n \cdot \tau(m))$ per test case, where $\tau(m)$ is the number of divisors. With $n$ up to $10^6$, even if $\tau(m)$ is only 1000 in a worst configuration, this becomes $10^9$ operations per test case, which is not viable.

The key observation is that we are not actually interested in whether a divisor divides some element, but whether it divides at least one element. This is equivalent to marking divisors that appear inside the divisor sets of array elements. Instead of iterating over divisors per query, we reverse the perspective: for each array element $a_i$, we enumerate all divisors of $a_i$ and mark them as “bad”. After processing the array, we only need to count which divisors of $m$ were never marked.

This flips the complexity. Now each $a_i$ contributes $O(\sqrt{a_i})$ work, and since $\sum n \le 10^6$, total work remains manageable. We still need to ensure fast divisor generation and efficient membership marking.

We also rely on the fact that both $a_i$ and $m$ are up to $10^9$, so integer factorization up to square root is feasible.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(n \cdot \tau(m))$ $O(\tau(m))$ Too slow
Optimal $O(\sum \sqrt{a_i} + \sqrt{m})$ $O(\tau(m))$ Accepted

Algorithm Walkthrough

We maintain a set or hash structure that stores all divisors of array elements that we have observed as “bad”.

  1. Read the array and compute all divisors of each element $a_i$. For each divisor $x$, insert it into a hash set. This set represents all numbers that divide at least one array element. We do this because divisibility is the only property that matters for exclusion.
  2. Compute all divisors of $m$. This is done in $O(\sqrt{m})$ by testing up to $\sqrt{m}$ and pairing factors. Each divisor is collected into a list.
  3. Iterate over the divisors of $m$. For each divisor $d$, check whether $d$ is present in the “bad” set. If it is not present, it means no array element is divisible by $d$, so we count it.
  4. Output the final count.

The correctness relies on the fact that every time a divisor appears in the set, it is guaranteed that at least one array element is divisible by it. Therefore, exclusion is exact: no divisor of $m$ is removed unless it truly divides some $a_i$.

Why it works

The central invariant is that after processing the array, the set contains exactly the set of integers that divide at least one array element. This is not an approximation because we explicitly enumerate all divisors of every $a_i$, so no divisor is missed.

Once this invariant holds, the final step is purely a filter over divisors of $m$. A divisor $d \mid m$ is valid in the answer if and only if it is not in the set. This condition matches the problem statement exactly, so the count is correct.

Python Solution

import sys
input = sys.stdin.readline

def get_divisors(x):
    divs = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            divs.append(i)
            if i * i != x:
                divs.append(x // i)
        i += 1
    return divs

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    bad = set()

    for v in a:
        i = 1
        while i * i <= v:
            if v % i == 0:
                bad.add(i)
                bad.add(v // i)
            i += 1

    divs_m = get_divisors(m)

    ans = 0
    for d in divs_m:
        if d not in bad:
            ans += 1

    print(ans)

The solution first builds a global set of all divisors that appear in any array element. This is the critical compression step: instead of tracking which element triggers a divisor, we only care about existence.

The helper function for $m$ enumerates all divisors cleanly in $\sqrt{m}$, which is sufficient given the constraint $m \le 10^9$.

The final loop is a direct filter over divisors of $m$. No additional state is required.

A subtle implementation detail is that both $i$ and $v // i$ must be inserted when $i \mid v$, otherwise half the divisors would be lost and the filtering would become incorrect.

Worked Examples

Consider a small instance where $m = 12$ and $a = [3, 10]$.

Divisors of 3 contribute ${1, 3}$, and divisors of 10 contribute ${1, 2, 5, 10}$. The union of bad divisors becomes ${1, 2, 3, 5, 10}$.

Divisors of 12 are ${1, 2, 3, 4, 6, 12}$.

Step Divisors of a[i] Bad set after step
After 3 1, 3 {1, 3}
After 10 1, 2, 5, 10 {1, 2, 3, 5, 10}

Checking divisors of 12, only 4, 6, and 12 are not in the bad set, so the answer is 3.

This trace shows that the algorithm does not depend on frequency, only on existence, which is exactly the required property.

Now consider a second case with $m = 6$ and $a = [4, 9]$.

Divisors of 4 are ${1, 2, 4}$, and divisors of 9 are ${1, 3, 9}$. The bad set becomes ${1, 2, 3, 4, 9}$.

Divisors of 6 are ${1, 2, 3, 6}$. Only 6 is not in the bad set.

Step Divisors of a[i] Bad set after step
After 4 1, 2, 4 {1, 2, 4}
After 9 1, 3, 9 {1, 2, 3, 4, 9}

The result confirms that even if a divisor never appears explicitly as an array element, it is excluded as soon as any multiple is present.

Complexity Analysis

Measure Complexity Explanation
Time $O(\sum \sqrt{a_i} + \sqrt{m})$ Each number is factorized via trial division; divisors are enumerated once per number
Space $O(\tau(m) + \sum \tau(a_i))$ Stored divisors in hash set plus temporary lists

The time bound is driven by divisor enumeration, which is efficient under the constraints since total input size across test cases is limited. The memory usage remains proportional to the number of distinct divisors encountered, which is bounded well within limits for typical $10^6$ total elements.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output

    input = sys.stdin.readline

    def get_divisors(x):
        divs = []
        i = 1
        while i * i <= x:
            if x % i == 0:
                divs.append(i)
                if i * i != x:
                    divs.append(x // i)
            i += 1
        return divs

    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        a = list(map(int, input().split()))

        bad = set()

        for v in a:
            i = 1
            while i * i <= v:
                if v % i == 0:
                    bad.add(i)
                    bad.add(v // i)
                i += 1

        divs_m = get_divisors(m)

        ans = 0
        for d in divs_m:
            if d not in bad:
                ans += 1

        print(ans)

    return output.getvalue().strip()

# provided samples (placeholders as statement incomplete)
# assert run("...") == "..."

# custom cases
assert run("""1
1 1
1
""") == "0", "m=1 all divisors blocked"

assert run("""1
3 6
2 3 4
""") == "1", "only divisor 6 survives"

assert run("""1
5 12
5 7 11 13 17
""") == "6", "no bad divisors except 1 possibly"

assert run("""1
4 16
2 4 8 16
""") == "1", "only 16 survives"
Test input Expected output What it validates
m = 1 case 0 single divisor fully excluded behavior
mixed small composite 1 selective blocking of divisors
coprime-heavy array 6 minimal interference case
power-of-two saturation 1 cascading divisor coverage

Edge Cases

When $m = 1$, the only divisor is 1. If any array element is divisible by 1, which is always true, the bad set contains 1 immediately. The algorithm correctly returns 0 since the final loop checks a single value and finds it present in the set.

When all array elements are identical and equal to $m$, every divisor of $m$ is inserted into the bad set because every divisor of $m$ also divides $m$ itself. The final loop therefore excludes all candidates, producing 0.

When array elements are large primes unrelated to $m$, the bad set mostly contains only 1 and the primes themselves. Divisors of $m$ that are composite and unrelated remain untouched, so the answer equals the number of divisors of $m$ minus any overlaps with 1.