Overview

We simulate the patrol according to the rules while managing the set of unchecked servers.
The key is to quickly find the “minimum unchecked number that shares a prime factor with the current number \(k\)”.

Analysis

Let \(k\) be the current server number.

When \(k \geq 2\), the next number \(m\) we can move to must satisfy:

\[ \gcd(k, m) \geq 2 \]

In other words,

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

For example, if \(k = 12\), its prime factors are \(2\) and \(3\), so the next possible numbers are multiples of \(2\) or multiples of \(3\).

Therefore, the next number to move to is:

the minimum among the smallest unchecked multiples of \(p\) that are greater than \(k\), for each prime factor \(p\) of \(k\).

---

If we naively check \(k+1, k+2, \dots, N\) in order and compute \(\gcd(k,m)\) every time, it would take about \(O(N^2 \log N)\) in the worst case, which will not run in time for \(N \leq 5 \times 10^5\).

Therefore, we need to quickly perform the following operations:

• Find the minimum among all unchecked numbers.
• For a prime \(p\), find the minimum unchecked multiple of \(p\) at or after a specified position.

To do this, we use Union-Find as a data structure to skip deleted elements and find the next undeleted element.

Algorithm

1. Precompute the smallest prime factors

First, we compute the smallest prime factor spf[x] for each integer \(x\).

This allows us to quickly list the prime factors of any \(x\).

For example, if

\[ 12 = 2^2 \times 3 \]

we extract \(2\) and \(3\) as its prime factors.

---

2. Manage the overall set of unchecked numbers

At the start of a patrol, we need to choose:

the smallest number among the unchecked servers.

To achieve this, we prepare a Union-Find to find the “smallest remaining number” among all \(1, 2, \dots, N\).

A deleted number \(x\) will be pointed (skipped) to the next number \(x+1\).

That is, by setting:

global_parent[x] = find_root(global_parent, x + 1);

\(x\) will be skipped in subsequent searches. Calling find_root(global_parent, 1) will yield the current minimum unchecked number.

---

3. Manage “unchecked multiples” for each prime

Next, for each prime \(p\), we consider the sequence of multiples of \(p\):

\[ p, 2p, 3p, \dots \]

For example, if \(p=3\) and \(N=15\), the sequence is:

\[ 3, 6, 9, 12, 15 \]

We also use Union-Find on this sequence to skip deleted multiples.

Once a number \(x\) is checked, we delete \(x\) from the “sequence of multiples of \(p\)” for each prime factor \(p\) of \(x\).

For example, if \(x=12\), its prime factors are \(2\) and \(3\), so we:

• Delete \(12\) from the sequence of multiples of \(2\).
• Delete \(12\) from the sequence of multiples of \(3\).

---

4. Find the next number to move to

Let the current number be \(k\).

Case \(k=1\)

Since \(1\) has no prime factors, we handle it as a special case as described in the problem statement.

We just need to find the smallest unchecked number greater than \(1\).

This can be found with:

find_root(global_parent, 2)

Case \(k \geq 2\)

We list the prime factors of \(k\).

For each prime factor \(p\):

find the smallest unchecked multiple of \(p\) that is greater than \(k\).

The minimum among these candidates will be the next number to move to.

For example, if \(k=12\), its prime factors are \(2\) and \(3\).

• The smallest unchecked multiple of \(2\) greater than \(12\)
• The smallest unchecked multiple of \(3\) greater than \(12\)

We check both and choose the smaller one.

This correctly finds the minimum \(m\) satisfying the condition:

\[ \gcd(k,m) \geq 2 \]

---

5. Actual Simulation

The overall flow is as follows:

1. Find the minimum unchecked number \(s\).
2. If it does not exist, terminate.
3. Increment the number of patrols by \(1\).
4. Mark \(s\) as checked.
5. Find the next number we can move to from the current position.
6. If found, mark it as checked and move to it.
7. If not found, end the current patrol and return to step 1.

Since each number is marked as checked at most once, the overall process is highly efficient.

Complexity

• Time Complexity: Around \(O(N \log \log N)\)
• Space Complexity: Around \(O(N \log \log N)\)

For each integer, we process its distinct prime factors.
The sum of the number of distinct prime factors from \(1\) to \(N\) is around \(O(N \log \log N)\).

Also, since we manage the sequence of multiples for each prime \(p\), the total number of elements required is:

\[ \sum_{p \leq N} \left\lfloor \frac{N}{p} \right\rfloor \]

which is also around \(O(N \log \log N)\).

Implementation Details

Finding the “next undeleted element” with Union-Find

The usage is slightly different from the standard Union-Find.

For a deleted element \(x\), we do:

parent[x] = find_root(parent, x + 1);

By doing so, find_root(parent, x) will return the smallest element greater than or equal to \(x\) that has not been deleted yet.

---

Processing prime factors without duplicates

For example, \(12 = 2^2 \times 3\), but the prime factors to process are only \(2\) and \(3\).

In the code, we do:

while (t % p == 0) t /= p;

to skip identical prime factors all at once.

---

Packing the sequences of multiples for all primes into a single array

Conceptually, we have a separate Union-Find array for each prime \(p\).

However, in the implementation, we pack all of them into a single array mult_parent.

offset[p] represents where the sequence of multiples of prime \(p\) begins in mult_parent.

For example, a multiple \(x\) of \(p\) can be written as \(x = jp\), which corresponds to the \((j-1)\)-th element in the sequence of multiples.

Therefore, in the code, we calculate the position as:

idx = offset[p] + x / p - 1;

Source Code

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

static inline int find_root(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> spf(N + 1, 0), primes;
    for (int i = 2; i <= N; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || 1LL * i * p > N) break;
            spf[i * p] = p;
        }
    }

    vector<int> offset(N + 1, -1);
    long long total = 0;
    for (int p : primes) {
        offset[p] = (int)total;
        total += N / p + 1;
    }

    vector<int> mult_parent((size_t)total);
    iota(mult_parent.begin(), mult_parent.end(), 0);

    vector<int> global_parent(N + 2);
    iota(global_parent.begin(), global_parent.end(), 0);

    auto erase_number = [&](int x) {
        global_parent[x] = find_root(global_parent, x + 1);

        int t = x;
        while (t > 1) {
            int p = spf[t];
            int idx = offset[p] + x / p - 1;
            mult_parent[idx] = find_root(mult_parent, idx + 1);
            while (t % p == 0) t /= p;
        }
    };

    auto get_next = [&](int k) {
        int res = N + 1;

        if (k == 1) {
            int v = find_root(global_parent, 2);
            return v <= N ? v : N + 1;
        }

        int t = k;
        while (t > 1) {
            int p = spf[t];
            int off = offset[p];
            int m = N / p;
            int idx = off + k / p;

            int r = find_root(mult_parent, idx);
            if (r < off + m) {
                int cand = (r - off + 1) * p;
                if (cand < res) res = cand;
            }

            while (t % p == 0) t /= p;
        }

        return res;
    };

    int answer = 0;

    while (true) {
        int s = find_root(global_parent, 1);
        if (s > N) break;

        answer++;
        int cur = s;
        erase_number(cur);

        while (true) {
            int nxt = get_next(cur);
            if (nxt > N) break;
            cur = nxt;
            erase_number(cur);
        }
    }

    cout << answer << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.