Overview

In each patrol, we move to the smallest uninspected server whose index is greater than the current index \(k\) and shares at least one common prime factor with \(k\).
We simulate this process efficiently to count the number of times a patrol is started.

Analysis

During a patrol, the destination we can move to is always an index greater than the current index.
Therefore, the sequence of indices visited in each patrol is strictly increasing, and each server is inspected exactly once.

Limitations of the Naive Approach

If we let the current position be \(k\), and to find the next server we repeatedly:

• Check \(k+1, k+2, \dots, N\) in order
• Determine for each whether \(\gcd(k, m) \geq 2\)

this approach would take \(O(N^2)\) time in the worst case, which is too slow for \(N \leq 5 \times 10^5\).

Key Observation

For \(k \geq 2\), the condition that an index \(m\) shares a common prime factor with \(k\) is equivalent to:

\(m\) is divisible by at least one of the prime factors of \(k\).

For example, the prime factors of \(k = 6\) are \(2\) and \(3\).
In this case, the next candidates are:

• Uninspected multiples of \(2\)
• Uninspected multiples of \(3\)

that are strictly greater than \(k\).

Therefore, for each prime factor \(p\) of \(k\), we can find:

the minimum uninspected multiple of \(p\) that is strictly greater than \(k\)

and then take the minimum among all these values.

Finding the Minimum Uninspected Value Efficiently

To “skip deleted elements and find the next remaining element”, we can use a “next pointer” structure similar to a Union-Find.

We prepare a parent array. When an index \(x\) is marked as inspected, we set:

\[ parent[x] = find(x+1) \]

With this, find(x) will return the minimum uninspected index that is greater than or equal to \(x\).

We prepare two types of such structures:

1. Overall Structure

   • Finds the minimum among all uninspected indices.
   • Used when starting a new patrol or for the special case of \(k=1\).

2. Structure for Multiples of Each Prime \(p\)

   • Finds the minimum uninspected multiple of \(p\) specifically among multiples of \(p\).
   • In practice, we manage the multiple \(p \times q\) using the index \(q\).

Algorithm

First, for each integer \(x\), we precompute the list of its prime factors factors[x].

However, we can ignore prime factors \(p > \frac{N}{2}\).
This is because for \(p > \frac{N}{2}\), there is no multiple of \(p\) other than \(p\) itself that is less than or equal to \(N\), so we can never move to a larger multiple of \(p\).

Precomputation

1. Let \(H = \lfloor N/2 \rfloor\).
2. List all prime numbers up to \(H\) using the Sieve of Eratosthenes.
3. For each prime \(p\):
   • Add \(p\) as a prime factor to \(p, 2p, 3p, \dots\).
   • Prepare a Union-Find array to manage the multiples of \(p\).

Inspection Process

When a server \(x\) is inspected:

• Remove \(x\) from the overall Union-Find.
• For each prime factor \(p\) of \(x\), remove \(x\) from the Union-Find managing the multiples of \(p\).

Specifically, if \(x = p \times q\), we remove the index \(q\) in the management array for the prime \(p\).

Simulation of Patrols

While there are still uninspected servers, repeat the following:

1. Find the smallest uninspected index \(s\) using the overall Union-Find.
2. Increment the answer by \(1\) since a new patrol is starting.
3. Set the current position to \(k=s\), and mark \(k\) as inspected.
4. Find the next server:
   • If \(k=1\):
     Find the smallest uninspected index \(\geq 2\) using the overall Union-Find.
   • If \(k \geq 2\):
     For each prime factor \(p\) of \(k\), find the smallest uninspected multiple of \(p\) that is strictly greater than \(k\).
     Set the minimum among these values as the next server.
5. If the next server does not exist, terminate the current patrol.
6. If it exists, move to that server and continue the process.

For example, if \(k=6\), its prime factors are \(2\) and \(3\).
If the smallest candidate uninspected multiple of \(2\) is \(8\) and that of \(3\) is \(9\), the next destination is \(8\).

Complexity

• Time Complexity: \(O(N \log \log N \cdot \alpha(N))\)
• Space Complexity: \(O(N \log \log N)\)

Here, \(\alpha(N)\) is the inverse Ackermann function from Union-Find, which is practically a constant.

The total number of prime factors we examine across all numbers \(x\) is:

\[ \sum_{p \leq N/2} \left\lfloor \frac{N}{p} \right\rfloor = O(N \log \log N) \]

Thus, the entire process can be executed very quickly.

Key Implementation Points

• The overall Union-Find is used to find the “minimum uninspected index”.

• For the Union-Find of each prime \(p\), the index \(q\) corresponds to the server number \(p \times q\).

• When looking for a multiple of \(p\) greater than \(k\), we perform a find operation starting from \(q = \frac{k}{p} + 1\).

• Placing a sentinel at index \(N+1\) (and at the end of each prime’s array) makes it easier to handle the case where “the next element does not exist”.

• Prime factors do not need to be stored with multiplicity. For example, even though \(12 = 2^2 \times 3\), we only need to store \(2\) and \(3\).

  Source Code

import sys
from math import isqrt

def main():
    N = int(sys.stdin.buffer.readline())
    H = N // 2

    factors = [[] for _ in range(N + 1)]
    parents = [None] * (H + 1)

    if H >= 2:
        is_prime = bytearray(b'\x01') * (H + 1)
        is_prime[0] = 0
        is_prime[1] = 0

        for i in range(2, isqrt(H) + 1):
            if is_prime[i]:
                start = i * i
                is_prime[start:H + 1:i] = b'\x00' * (((H - start) // i) + 1)

        for p in range(2, H + 1):
            if is_prime[p]:
                parents[p] = list(range(N // p + 2))
                for j in range(p, N + 1, p):
                    factors[j].append(p)

    gpar = list(range(N + 2))
    INF = N + 1

    def gfind(x):
        while gpar[x] != x:
            gpar[x] = gpar[gpar[x]]
            x = gpar[x]
        return x

    def visit(x):
        y = x + 1
        while gpar[y] != y:
            gpar[y] = gpar[gpar[y]]
            y = gpar[y]
        gpar[x] = y

        fs = factors[x]
        for p in fs:
            par = parents[p]
            idx = x // p
            y = idx + 1
            while par[y] != y:
                par[y] = par[par[y]]
                y = par[y]
            par[idx] = y
        return fs

    ans = 0

    while True:
        s = gfind(1)
        if s > N:
            break

        ans += 1
        k = s
        fs = visit(k)

        while True:
            if k == 1:
                nxt = gfind(2)
            else:
                nxt = INF
                for p in fs:
                    par = parents[p]
                    idx = k // p + 1
                    y = idx
                    while par[y] != y:
                        par[y] = par[par[y]]
                        y = par[y]
                    cand = p * y
                    if cand < nxt:
                        nxt = cand

            if nxt > N:
                break

            k = nxt
            fs = visit(k)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.